最小覆盖子矩阵问题

题目描述

每天早上，农夫约翰的奶牛们被挤奶的时候，都会站成一个 $R$ 行 $C$ 列的方阵。

现在在每个奶牛的身上标注表示其品种的大写字母，则所有奶牛共同构成了一个 $R$ 行 $C$ 列的字符矩阵。

现在给定由所有奶牛构成的矩阵，求它的最小覆盖子矩阵的面积是多少。

如果一个子矩阵无限复制扩张之后得到的矩阵能包含原来的矩阵，则称该子矩阵为覆盖子矩阵。

输入格式

第 1 行：输入两个用空格隔开的整数，$R$ 和 $C$。

第 2..R+1 行：描绘由奶牛构成的 $R$ 行 $C$ 列的矩阵，每行 $C$ 个字符，字符之间没有空格。

输出格式

输出最小覆盖子矩阵的面积。（每个字符的面积为 1）

输入输出样例 #1

输入样例

2 5
ABABA
ABABA

输出样例

2

限制条件

• $1 \le R \le 10000$
• $1 \le C \le 75$

时间限制

1秒

空间限制

64MB

样例解释

给定矩阵（$2 \times 5$）：

ABABA
ABABA

覆盖子矩阵定义分析

覆盖子矩阵：一个子矩阵，当它被无限复制扩张后，能够得到原始矩阵。

对于这个例子：

• 原始矩阵可以看作是子矩阵 AB 的重复：

  AB AB A  ← 但实际上最后多出一个A
  AB AB A
  

  这不完全匹配。

实际上检查：

• 如果取子矩阵宽度为2：AB

  • 第1行：AB重复得到 ABABAB...，但原矩阵是 ABABA，最后一个字符是A，匹配
  • 第2行相同
  • 所以 AB 是一个覆盖子矩阵，面积 = 1行 × 2列 = 2

• 如果取子矩阵宽度为1：A

  • 重复得到 AAAAA...，但原矩阵有B，不匹配

• 如果取子矩阵宽度为5：就是原矩阵本身，面积 = 2 × 5 = 10

所以最小覆盖子矩阵是 AB，面积为 2。

更一般的情况

设最小覆盖子矩阵的尺寸为 $h \times w$，其中：

• $h$ 是覆盖子矩阵的行数
• $w$ 是覆盖子矩阵的列数

这个子矩阵必须满足：

1. 对于任意 $i$ 和 $j$，有 $matrix[i][j] = matrix[i \bmod h][j \bmod w]$
2. $h$ 和 $w$ 尽可能小，使得 $h \times w$ 最小

换句话说：

• 在列方向：矩阵的每一行必须是由一个长度为 $w$ 的模式重复构成
• 在行方向：矩阵的每一列必须是由一个长度为 $h$ 的模式重复构成