다이아몬드 광산

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

어려움8동적 계획법이분 탐색기하행렬아직 제출이 없습니다시간 제한0.75초메모리 제한128 MB

문제 설명

예제4

문제

다이아몬드 광산은 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을 출력한다.