字母矩阵

[编程题]字母矩阵

热度指数：560 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

一个 $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

说明

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

算法知识视频讲解

相依相随

发表于 2021-09-02 11:58:21

思路二维矩阵前缀和，sum[i][j][l]代表在以（i,j）右下角点的矩形中第l个字母的数量，二分正方形的边长，看在这个边长中能否找到一个正方形满足条件。代码 import java.io.BufferedInputStream; import java.util.Arrays; import 展开全文