#P4330. [COCI2006-2007#1] Debug

[COCI2006-2007#1] Debug

题目描述

While debugging a program Mirko noticed that a bug in the program may be linked with the existence of so called square killers in the program memory. The program memory is a matrix composed of R rows and C columns consisting only of zeroes and ones. A square killer is a square submatrix in memory, consisting of more than one character, that, when rotated 180 degrees looks exactly the same. For example, the following matrix contains 3 square killers:

Mirko is wondering if there is a connection between the size of the largest square killer and the bug in the program. Help Mirko by writing a program that, given the layout of the memory, outputs the size of the largest square killer. The size of the square killer is the number of rows (or columns) that the killer consists of. In the example above the killer sizes are 2, 2 and 3, respectively.

输入格式

The first will contain two integers, R and C, smaller than or equal to 300. The next R lines will each contain C characters ('0' or '1') with no spaces.

输出格式

Output the size of the largest killer on a single line, or output -1 if there are no square killers.

题目大意

Mirko在写bug的时候,注意到这样一个问题:程序中的bug可能与内存中的”square killer”有关。程序的内存是一个r行c列的01矩阵。”square killer”是其中包含一个以上字符的一个正方形子矩阵,而且”square killer”旋转180°后与原来相同。例如,下面的矩阵中含有三个”square killer”:

Mirko想知道程序中最大的”square killer”与bug的联系。帮助他写一个程序,求出最大的”square killer”的大小。”square killer”的大小是指它含有的行数或列数。图中的”square killer”的大小分别是2、2、3。

Translated by @ACdreamer

3 6
101010
111001
101001
3
4 5
10010
01010
10101
01001
3
3 3
101
111
100
-1