텍스처 타일

시간 제한2초메모리 제한256 MB

요약

N x N 이미지가 주어질 때, 첫 행과 마지막 행이 같고 첫 열과 마지막 열이 같은 가장 큰 정사각 부분 이미지의 한 변 길이를 구한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 해시맵, 이분 탐색
정답자: 아직 제출이 없습니다

문제

정사각형 래스터 이미지는 $N \times N$ 픽셀 배열로 표현된다. 텍스처 타일(texture tile)이란, 첫 번째 행이 마지막 행과 완전히 같고 첫 번째 열이 마지막 열과 완전히 같은 정사각형 (부분)이미지를 말한다. 이 성질은 텍스처를 반복해서 이어 붙여 그래픽 객체의 표면을 덮을 때 유용한데, 인접한 복사본들이 "이음매 없이(seamless)" 자연스럽게 연결되도록 해 주기 때문이다.

주어진 이미지에서, 텍스처 타일이 되는 가장 큰 정사각형 부분이미지의 한 변의 길이를 구하여라.

입력

첫 번째 정수는 $N$ 이다. 그 뒤에 픽셀 값인 정수 $N^2$ 개 $c_{i,j}$ 가 행 단위로(1번 행부터 차례대로) 주어진다.

출력

이미지에 포함된 가장 큰 텍스처 타일의 한 변의 길이 $m$ 을 정수 하나로 출력하여라. (픽셀 하나도 항상 텍스처 타일이므로 언제나 $m \ge 1$ 이다.)

제한

$1 \le N \le 370$
$0 \le c_{i,j} \le 255$

예제4

예제 1
입력
```
2
0 0
2 3
```
예상 출력
```
1
```
예제 2
입력
```
4
1 0 0 0
1 2 5 2
1 0 0 0
4 4 4 4
```
예상 출력
```
3
```
예제 3
입력
```
1
5
```
예상 출력
```
1
```
예제 4
입력
```
2
5 5
5 5
```
예상 출력
```
2
```