디버그

시간 제한5초메모리 제한128 MB

요약

0과 1로 이루어진 R by C 행렬에서 180도 회전해도 같은 모양을 유지하는 가장 큰 정사각형(한 변이 2 이상)의 크기를 구하고, 없으면 -1을 출력합니다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 행렬, 완전 탐색
정답자: 아직 제출이 없습니다

문제

상근이는 프로그램을 디버깅하다가, 프로그램 메모리 안의 어떤 정사각형 패턴이 버그와 깊은 관련이 있다는 사실을 알게 되었다.

프로그램 메모리는 0과 1로만 이루어진 R행 C열 행렬이다.

정사각형 킬러는 한 글자보다 큰 정사각형 부분 행렬 중에서, 그 부분 행렬을 180도 회전해도 원래 모습과 같은 것이다. 즉, 크기가 K인 정사각형 킬러는 모든 0 <= i, j < K에 대해 왼쪽 위에서 (i, j)에 있는 문자와 오른쪽 아래에서 대칭인 (K-1-i, K-1-j)에 있는 문자가 같다.

프로그램 메모리가 주어졌을 때, 가장 큰 정사각형 킬러의 크기를 구하시오. 정사각형 킬러의 크기는 부분 행렬의 행 개수이자 열 개수이다.

입력

첫째 줄에 300보다 작거나 같은 자연수 R과 C가 주어진다.

다음 R개의 줄에는 길이가 C인 문자열이 주어진다. 각 문자는 0 또는 1이며, 문자 사이에 공백은 없다.

출력

가장 큰 정사각형 킬러의 크기를 출력한다.

정사각형 킬러가 하나도 없다면 -1을 출력한다.

예제3

예제 1
입력
```
3 6
101010
111001
101001
```
예상 출력
```
3
```
예제 2
입력
```
4 5
10010
01010
10101
01001
```
예상 출력
```
3
```
예제 3
입력
```
3 3
101
111
100
```
예상 출력
```
-1
```