시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 662 271 179 40.225%

문제

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

입력

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

출력

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

예제 입력 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

예제 출력 1

3
3
0

힌트

W3sicHJvYmxlbV9pZCI6IjQwOTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNkNWNcdWIzMDAgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHQxXHVhY2ZjIDBcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IE54TVx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWQ1ODlcdWI4MmNcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgMVx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHViZDgwXHViZDg0IFx1ZDU4OVx1YjgyYyBcdWNjM2VcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IE5cdWFjZmMgTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTixNICZsZTsgMSwwMDApIFx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDFjIE1cdWFjMWNcdWM3NTggXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1YjQ1MCBcdWFjMWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWIxMDhcdWJlNDQgXHViNjEwXHViMjk0IFx1YjE5Mlx1Yzc3NFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWFkZjhcdWI3ZjAgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0IFx1YzVjNlx1Yzc0NCBcdWI1NGNcdWIyOTQgMFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDA5NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1heGltdW0gU3F1YXJlIiwiZGVzY3JpcHRpb24iOiI8cD5HaXZlbiBhbiBOeE0gbWF0cml4IG9mIGFsbCAxcyBhbmQgMHMsIGZpbmQgdGhlIGxhcmdlc3Qgc3VibWF0cml4IHdoaWNoIGlzIGEgc3F1YXJlIGNvbnRhaW5pbmcgYWxsIDFzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlcmUgd2lsbCBiZSBzZXZlcmFsIHRlc3QgY2FzZXMgaW4gdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSB3aWxsIGJlZ2luIHdpdGggdHdvIGludGVnZXJzLCBOIGFuZCBNICgxICZsZTsgTixNICZsZTsgMSwwMDApIGluZGljYXRpbmcgdGhlIG51bWJlciBvZiByb3dzIGFuZCBjb2x1bW5zIG9mIHRoZSBtYXRyaXguIFRoZSBuZXh0IE4gbGluZXMgd2lsbCBlYWNoIGNvbnRhaW4gTSBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMsIGd1YXJhbnRlZWQgdG8gYmUgZWl0aGVyIDAgb3IgMS4gVGhlIGlucHV0IHdpbGwgZW5kIHdpdGggYSBsaW5lIHdpdGggdHdvIDBzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgcHJpbnQgYSBzaW5nbGUgaW50ZWdlciwgaW5kaWNhdGluZyB0aGUgd2lkdGggKGFuZCBoZWlnaHQpIG9mIHRoZSBsYXJnZXN0IHNxdWFyZSBvZiBhbGwgMXMsIG9yIDAgaWYgdGhlcmUgYXJlIG5vIDFzLiBQcmludCBubyBleHRyYSBzcGFjZXMsIGFuZCBkbyBub3QgcHJpbnQgYW55IGJsYW5rIGxpbmVzIGJldHdlZW4gYW5zd2Vycy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=