다이아몬드 광산

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

요약

0과 1로 이루어진 R행 C열 격자에서 1로만 이루어진 45도 회전 정사각형 테두리(다이아몬드)의 최대 크기를 구합니다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 이분 탐색, 기하, 행렬
정답자: 아직 제출이 없습니다

문제

다이아몬드 광산은 0과 1로 이루어진 R행 C열 격자이다.

다이아몬드는 1로 이루어진 정사각형의 테두리를 45도 돌린 모양이다. 크기가 1, 2, 3인 다이아몬드는 다음과 같다.

size 1:    size 2:    size 3:
                         1
              1         1 1
   1         1 1       1   1
              1         1 1
                         1

격자 안에서 만들 수 있는 가장 큰 다이아몬드의 크기를 구하시오.

입력

첫째 줄에 R과 C가 주어진다. R과 C는 각각 750 이하의 자연수이다. 다음 R개의 줄에는 다이아몬드 광산의 각 행이 0과 1로 주어진다.

출력

첫째 줄에 다이아몬드 광산에서 찾을 수 있는 가장 큰 다이아몬드의 크기를 출력한다. 다이아몬드가 하나도 없으면 0을 출력한다.

예제4

예제 1
입력
```
5 5
01100
01011
11111
01111
11111
```
예상 출력
```
3
```
예제 2
입력
```
5 5
01100
00011
11111
01111
11111
```
예상 출력
```
2
```
예제 3
입력
```
4 4
0000
0000
0000
0000
```
예상 출력
```
0
```
예제 4
입력
```
3 6
111000
101111
111111
```
예상 출력
```
2
```