首页 > 试题广场 >

字母矩阵

[编程题]字母矩阵

一个 $n \times m$ 的只由小写英文字母组成的矩阵 $A$ ，牛牛想找到一个面积最小的正方形子矩阵满足该正方形子矩阵包含至少 $k$ 种不同的字母。

第一行输入三个正整数 $n,m,k$ 。

接下来 $n$ 行每行输入一个长度为 $m$ 的字符串，其中第 $i$ 行第 $j$ 个字母为 $A_{i,j}$ 。

$(1 \leq n,m \leq 500,1 \leq k \leq 26,A_{i,j} \in S)$

其中 $S$ 为所有小写英文字母'a'-'z'的集合。

输出一个正整数表示包含至少  种不同字母的方形子矩阵的边长，如果不存在该子方阵，输出。

示例1

输入

4 4 3
aabc
aaaa
axaz
abcd

不存在边长为  的方形子矩阵包含至少  种不同的字母。
如图，存在边长为  的方形子矩阵包含至少  种不同的字母：

示例2

2 2 5
ab
cd

-1

显然矩阵总共只有 种字符，因此答案为  。

算法知识视频讲解

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

C++工程师 golang工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师测试工程师 PHP工程师安全工程师游戏研发工程师 2021 数据库工程师信息技术岗区块链测试开发工程师大数据开发工程师数据分析师牛客

上传者：小小

难度：

0条回答 39收藏 3093浏览

扫一扫，把题目装进口袋