2270: Minimum coverage matrix
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:3
解决:1
题目描述
Give you a character matrix, you need to find a sub matrix which can “cover” the whole matrix, and its size should be minimum.
In addition, you must assure that the left-top element is in the sub matrix. For example:
ABCDEFAB
AAAABAAA
ABCDEFAB
We can find the following minimum coverage matrix:
ABCDEF
AAAABA
Because by extension we can get:
ABCDEFABCDEF
AAAABAAAAABA
ABCDEFABCDEF
AAAABAAAAABA
We see it contains the original matrix.
输入
First line contains a integer T(1<=T<=30), indicating the case count.
For each case, first line contains two integers R(1<=R<=500) and C(1<=C<=500),
seperated by a space, there will be a R*C character matrix next.
输出
The size of minimum coverage matrix in a line.
样例输入 复制
3
3 8
ABCDEFAB
AAAABAAA
ABCDEFAB
2 8
ABCDEFAB
AAAABAAA
1 1
A
样例输出 复制
12
12
1