시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 128 MB86624615829.644%

문제

상근이는 프로그램을 디버깅할 때, 버그와 프로그램 메모리에서 정사각형 킬러가 깊은 관계가 있다는 것을 알게 되었다.

프로그램 메모리는 1과 0으로만 이루어진 R행 C열 행렬로 이루어져 있다.

정사각형 킬러란 프로그램 메모리에서 한 글자보다 많은 문자로 이루어진 정사각형 부분 행렬 중에서, 180도 돌렸을 때와 원래 부분 행렬이 같은 것이다.

예를 들어, 프로그램 메모리가 아래 그림과 같을 때, 정사각형 킬러는 3가지가 있다.

상근이는 가장 큰 정사각형 킬러의 크기와 버그 사이의 관계가 궁금해졌다. 프로그램 메모리가 주어졌을 때, 가장 큰 정사각형 킬러의 크기를 구하는 프로그램을 작성하시오. 정사각형 킬러의 크기는 부분 행렬의 행의 개수 또는 열의 개수와 같다. 위의 그림에서 정사각형 킬러의 크기는 순서대로 2, 2, 3이다.

입력

첫째 줄에 300보다 작거나 같은 자연수 R과 C가 주어진다. 다음 R개의 줄에는 C개의 문자(0 또는 1)가 공백없이 주어진다.

출력

첫째 줄에 가장 큰 정사각형 킬러의 크기를 출력한다. 만약 정사각형 킬러가 없다면 -1을 출력한다.

예제 입력 1

3 6
101010
111001
101001

예제 출력 1

3

예제 입력 2

4 5
10010
01010
10101
01001

예제 출력 2

3

예제 입력 3

3 3
101
111
100

예제 출력 3

-1
W3sicHJvYmxlbV9pZCI6IjMwNTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI1MTRcdWJjODRcdWFkZjgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHViNTE0XHViYzg0XHVhZTQ1XHVkNTYwIFx1YjU0YywgXHViYzg0XHVhZGY4XHVjNjQwIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOCBcdWJhNTRcdWJhYThcdWI5YWNcdWM1ZDBcdWMxMWMgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1ZDBhY1x1YjdlY1x1YWMwMCBcdWFlNGFcdWM3NDAgXHVhZDAwXHVhY2M0XHVhYzAwIFx1Yzc4OFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDQgXHVjNTRjXHVhYzhjIFx1YjQxOFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTA0XHViODVjXHVhZGY4XHViN2E4IFx1YmE1NFx1YmFhOFx1YjlhY1x1YjI5NCAxXHVhY2ZjIDBcdWM3M2NcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFJcdWQ1ODkgQ1x1YzVmNCBcdWQ1ODlcdWI4MmNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1ZDBhY1x1YjdlY1x1Yjc4MCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YTggXHViYTU0XHViYWE4XHViOWFjXHVjNWQwXHVjMTFjIFx1ZDU1YyBcdWFlMDBcdWM3OTBcdWJjZjRcdWIyZTQgXHViOWNlXHVjNzQwIFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1YmQ4MFx1YmQ4NCBcdWQ1ODlcdWI4MmMgXHVjOTExXHVjNWQwXHVjMTFjLCAxODBcdWIzYzQgXHViM2NjXHViODM4XHVjNzQ0IFx1YjU0Y1x1YzY0MCBcdWM2ZDBcdWI3OTggXHViZDgwXHViZDg0IFx1ZDU4OVx1YjgyY1x1Yzc3NCBcdWFjMTlcdWM3NDAgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YTggXHViYTU0XHViYWE4XHViOWFjXHVhYzAwIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWFjZmMgXHVhYzE5XHVjNzQ0IFx1YjU0YywgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1ZDBhY1x1YjdlY1x1YjI5NCAzXHVhYzAwXHVjOWMwXHVhYzAwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9raWxsLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEwN3B4OyB3aWR0aDo2NzRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHVkMGFjXHViN2VjXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YzY0MCBcdWJjODRcdWFkZjggXHVjMGFjXHVjNzc0XHVjNzU4IFx1YWQwMFx1YWNjNFx1YWMwMCBcdWFkODFcdWFlMDhcdWQ1NzRcdWM4NGNcdWIyZTQuIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOCBcdWJhNTRcdWJhYThcdWI5YWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHVkMGFjXHViN2VjXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1ZDBhY1x1YjdlY1x1Yzc1OCBcdWQwNmNcdWFlMzBcdWIyOTQgXHViZDgwXHViZDg0IFx1ZDU4OVx1YjgyY1x1Yzc1OCBcdWQ1ODlcdWM3NTggXHVhYzFjXHVjMjE4IFx1YjYxMFx1YjI5NCBcdWM1ZjRcdWM3NTggXHVhYzFjXHVjMjE4XHVjNjQwIFx1YWMxOVx1YjJlNC4gXHVjNzA0XHVjNzU4IFx1YWRmOFx1YjliY1x1YzVkMFx1YzExYyBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHVkMGFjXHViN2VjXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YjI5NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgMiwgMiwgM1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgMzAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNzkwXHVjNWYwXHVjMjE4IFJcdWFjZmMgQ1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBSXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBDXHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MCgwIFx1YjYxMFx1YjI5NCAxKVx1YWMwMCBcdWFjZjVcdWJjMzFcdWM1YzZcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHVkMGFjXHViN2VjXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHVkMGFjXHViN2VjXHVhYzAwIFx1YzVjNlx1YjJlNFx1YmE3NCAtMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzA1NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkRFQlVHIiwiZGVzY3JpcHRpb24iOiI8cD5XaGlsZSBkZWJ1Z2dpbmcgYSBwcm9ncmFtIE1pcmtvIG5vdGljZWQgdGhhdCBhIGJ1ZyBpbiB0aGUgcHJvZ3JhbSBtYXkgYmUgbGlua2VkIHdpdGggdGhlIGV4aXN0ZW5jZSBvZiBzbyBjYWxsZWQgc3F1YXJlIGtpbGxlcnMgaW4gdGhlIHByb2dyYW0gbWVtb3J5LiBUaGUgcHJvZ3JhbSBtZW1vcnkgaXMgYSBtYXRyaXggY29tcG9zZWQgb2YgUiByb3dzIGFuZCBDIGNvbHVtbnMgY29uc2lzdGluZyBvbmx5IG9mIHplcm9lcyBhbmQgb25lcy4gQSBzcXVhcmUga2lsbGVyIGlzIGEgc3F1YXJlIHN1Ym1hdHJpeCBpbiBtZW1vcnksIGNvbnNpc3Rpbmcgb2YgbW9yZSB0aGFuIG9uZSBjaGFyYWN0ZXIsIHRoYXQsIHdoZW4gcm90YXRlZCAxODAgZGVncmVlcyBsb29rcyBleGFjdGx5IHRoZSBzYW1lLiBGb3IgZXhhbXBsZSwgdGhlIGZvbGxvd2luZyBtYXRyaXggY29udGFpbnMgMyBzcXVhcmUga2lsbGVyczombmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9raWxsLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEwN3B4OyB3aWR0aDo2NzRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5NaXJrbyBpcyB3b25kZXJpbmcgaWYgdGhlcmUgaXMgYSBjb25uZWN0aW9uIGJldHdlZW4gdGhlIHNpemUgb2YgdGhlIGxhcmdlc3Qgc3F1YXJlIGtpbGxlciBhbmQgdGhlIGJ1ZyBpbiB0aGUgcHJvZ3JhbS4gSGVscCBNaXJrbyBieSB3cml0aW5nIGEgcHJvZ3JhbSB0aGF0LCBnaXZlbiB0aGUgbGF5b3V0IG9mIHRoZSBtZW1vcnksIG91dHB1dHMgdGhlIHNpemUgb2YgdGhlIGxhcmdlc3Qgc3F1YXJlIGtpbGxlci4gVGhlIHNpemUgb2YgdGhlIHNxdWFyZSBraWxsZXIgaXMgdGhlIG51bWJlciBvZiByb3dzIChvciBjb2x1bW5zKSB0aGF0IHRoZSBraWxsZXIgY29uc2lzdHMgb2YuIEluIHRoZSBleGFtcGxlIGFib3ZlIHRoZSBraWxsZXIgc2l6ZXMgYXJlIDIsIDIgYW5kIDMsIHJlc3BlY3RpdmVseS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCB3aWxsIGNvbnRhaW4gdHdvIGludGVnZXJzLCBSIGFuZCBDLCBzbWFsbGVyIHRoYW4gb3IgZXF1YWwgdG8gMzAwLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBSIGxpbmVzIHdpbGwgZWFjaCBjb250YWluIEMgY2hhcmFjdGVycyAoJiMzOTswJiMzOTsgb3IgJiMzOTsxJiMzOTspIHdpdGggbm8gc3BhY2VzLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgc2l6ZSBvZiB0aGUgbGFyZ2VzdCBraWxsZXIgb24gYSBzaW5nbGUgbGluZSwgb3Igb3V0cHV0IC0xIGlmIHRoZXJlIGFyZSBubyBzcXVhcmUga2lsbGVycy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2006/2007 > Contest #1 6번