최대 정사각형

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

요약

0과 1로 이루어진 행렬에서 모두 1로 채워진 가장 큰 정사각형 부분행렬의 한 변의 길이를 구한다.

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

문제

$0$ 과 $1$ 로 이루어진 $N \times M$ 크기의 행렬이 주어졌을 때, $1$ 로만 이루어진 가장 큰 정사각형 부분 행렬을 찾는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 $N$ 과 $M$ 이 주어진다 ( $1 \le N, M \le 1{,}000$ ). 다음 $N$ 개의 줄에는 공백으로 구분된 $M$ 개의 수가 주어진다. 마지막 줄에는 $0$ 이 두 개 주어진다.

출력

각 테스트 케이스에 대해, 가장 큰 정사각형의 한 변의 길이(너비 또는 높이)를 출력한다. 그런 정사각형이 없으면 $0$ 을 출력한다.

예제1

예제 1

입력

4 5
0 1 0 1 1
1 1 1 1 1
0 1 1 1 0
1 1 1 1 1
3 4
1 1 1 1
1 1 1 1
1 1 1 1
6 6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0

예상 출력

3
3
0