[BOJ 11873] 최대 직사각형

View as PDF

Submit solution

Points: 4
Time limit: 3.0s
Memory limit: 512M

Problem types
Allowed languages
Assembly, Awk, C, C++, Java, Pascal, Perl, Python, Sed, Text

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

입력 형식

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

출력 형식

각 테스트 케이스에 대해서 가장 큰 직사각형의 넓이를 출력한다. 만약 그런 직사각형이 없을 때는 0을 출력한다.

예제 입력

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

예제 출력

9
12
0

Comments

There are no comments at the moment.