TILING - Rectangle Tiling
We say that a 2-dimensional, rectangular word w of size n × m (imagine it as a board with letter written in the squares) can be tiled with a rectangular pattern p if there are such occurrences of p in w (but not necessarily all of them) that no two of them overlap and each symbol (square) of w is covered by one of them. Given such word w, find a rectangular pattern p of smallest size (area) which the word w can be tiled with.
Input
The first line of input contains a number t (1 ≤ t ≤ 100) that indicates the number of test cases to follow. Each test case begins with a line consisting of two positive integers n and m (1 ≤ n, m ≤ 1000) indicating dimensions of the board. n lines follow, each of them containing m small letters of the English alphabet (a, b ... z).
Output
For each test case output the smallest possible area of a pattern p that can be used to tile the given board.
Example
Input: 3 4 3 aaa aaa aaa aaa 4 4 abab cdcd abab cdcd 3 4 aaaa aaaa aaab Output: 1 4 12
hide comments
lokesh gopu:
2014-08-03 11:28:33
@ymGXX : 12 |
|
Xiaotao:
2013-05-08 08:09:19
3 4
|
|
ymGXX:
2013-05-08 08:09:19
3 4
|
|
Ravi Kiran:
2013-05-08 08:09:19
Get a very good runtime using gets()! |
Added by: | gawry |
Date: | 2007-11-10 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 |