직사각형 농지 구하기
면접 대비시간 제한2초메모리 제한512 MB
0과 1로 이루어진 5x5 격자마다 1만으로 이루어진 직사각형 중 가장 많은 1을 포함하는 넓이를 구한다.
문제
Karnaugh는 아주 작은 농지를 가진 가난한 농부다. 그는 왕국의 황무지를 개간해 새 농지를 얻으려고 한다. 그런데 반듯한 모양을 좋아하는 왕이 정착민은 직사각형 땅만 농지로 받을 수 있다는 규칙을 만들었다. 그래서 Karnaugh는 개간에 알맞은 가장 큰 직사각형 땅을 얻어야 한다.
황무지의 지도는 다음 그림과 같이 5 x 5 격자로 나타내며, '1'은 개간에 알맞은 곳, '0'은 모래땅을 나타낸다. 지도에서 1로만 이루어진 가장 큰 직사각형을 찾아 그 크기를 구하시오. 직사각형의 크기는 그 안에 들어 있는 1의 개수로 정의한다. 크기가 같은 가장 큰 직사각형이 둘 이상 있을 수 있다.
그림 1. 가장 큰 직사각형의 크기는 4다. 가장 큰 직사각형이 둘 있다(음영).
그림 2. 가장 큰 직사각형의 크기는 3이다. 가장 큰 직사각형이 하나 있다(음영).
입력
입력은 지도의 개수 m이 앞에 붙은 지도들로 이루어진다.
m
map1
map2
map3
...
mapm
두 지도는 빈 줄로 구분한다.
각 map**k는 다음 형식이다.
p p p p p
p p p p p
p p p p p
p p p p p
p p p p p
각 p는 '1' 또는 '0'인 문자다. 같은 줄에 있는 두 p는 공백 문자로 구분한다. 여기서 문자 '1'은 개간에 알맞은 곳, '0'은 모래땅을 나타낸다. 각 지도에는 '1'이 적어도 하나 들어 있다.
출력
각 입력 지도에 대해 가장 큰 직사각형의 크기를 한 줄에 하나씩 출력한다.