시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 1508 554 387 35.375%

문제

대략 위의 그림과 같이 생긴 성곽이 있다. 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타낸다. 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로그램을 작성하시오.

(1) 이 성에 있는 방의 개수

(2) 가장 넓은 방의 넓이

(3) 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기

위의 예에서는 방은 5개고, 가장 큰 방은 9개의 칸으로 이루어져 있으며, 위의 그림에서 화살표가 가리키는 벽을 제거하면 16인 크기의 방을 얻을 수 있다.

성은 m×n(1≤m, n≤50)개의 정사각형 칸으로 이루어진다. 성에는 최소 두 개의 방이 있어서, 항상 하나의 벽을 제거하여 두 방을 합치는 경우가 있다.

입력

첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어진다(이진수의 각 비트를 생각하면 쉽다). 따라서 이 값은 0부터 15까지의 범위 안에 있다.

출력

첫째 줄에 (1) 의 답을, 둘째 줄에 (2) 의 답을, 셋째 줄에 (3) 의 답을 출력한다.

예제 입력 1

7 4
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13

예제 출력 1

5
9
16
W3sicHJvYmxlbV9pZCI6IjIyMzQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxMzFcdWFjZmQiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMDhcL2Nhcy5QTkdcIiBzdHlsZT1cImhlaWdodDoxODlweDsgd2lkdGg6MzA3cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHViMzAwXHViN2I1IFx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YzBkZFx1YWUzNCBcdWMxMzFcdWFjZmRcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWFkNzVcdWM3NDAgXHVjMTIwXHVjNzQwIFx1YmNiZFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWFjZTAsIFx1YzgxMFx1YzEyMFx1Yzc0MCBcdWJjYmRcdWM3NzQgXHVjNWM2XHVjNWI0XHVjMTFjIFx1YzljMFx1YjA5OFx1YjJlNFx1YjJkMCBcdWMyMTggXHVjNzg4XHViMjk0IFx1ZDFiNVx1Yjg1Y1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWQ2MTVcdWQwZGNcdWM3NTggXHVjMTMxXHVjNzU4IFx1YzljMFx1YjNjNFx1Yjk3YyBcdWM3ODVcdWI4MjVcdWJjMWJcdWM1NDRcdWMxMWMgXHViMmU0XHVjNzRjXHVjNzQ0IFx1YWNjNFx1YzBiMFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD4oMSkgXHVjNzc0IFx1YzEzMVx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYzI5XHVjNzU4IFx1YWMxY1x1YzIxODxcL3A+XHJcblxyXG48cD4oMikgXHVhYzAwXHVjN2E1IFx1YjExM1x1Yzc0MCBcdWJjMjlcdWM3NTggXHViMTEzXHVjNzc0PFwvcD5cclxuXHJcbjxwPigzKSBcdWQ1NThcdWIwOThcdWM3NTggXHViY2JkXHVjNzQ0IFx1YzgxY1x1YWM3MFx1ZDU1OFx1YzVlYyBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHViMTEzXHVjNzQwIFx1YmMyOVx1Yzc1OCBcdWQwNmNcdWFlMzA8XC9wPlxyXG5cclxuPHA+XHVjNzA0XHVjNzU4IFx1YzYwOFx1YzVkMFx1YzExY1x1YjI5NCBcdWJjMjlcdWM3NDAgNVx1YWMxY1x1YWNlMCwgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWJjMjlcdWM3NDAgOVx1YWMxY1x1Yzc1OCBcdWNlNzhcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVjNzA0XHVjNzU4IFx1YWRmOFx1YjliY1x1YzVkMFx1YzExYyBcdWQ2NTRcdWMwYjRcdWQ0NWNcdWFjMDAgXHVhYzAwXHViOWFjXHVkMGE0XHViMjk0IFx1YmNiZFx1Yzc0NCBcdWM4MWNcdWFjNzBcdWQ1NThcdWJhNzQgMTZcdWM3NzggXHVkMDZjXHVhZTMwXHVjNzU4IFx1YmMyOVx1Yzc0NCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTMxXHVjNzQwIG0mdGltZXM7bigxJmxlO20sIG4mbGU7NTApXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWNlNzhcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0XHViMmU0LiBcdWMxMzFcdWM1ZDBcdWIyOTQgXHVjZDVjXHVjMThjIFx1YjQ1MCBcdWFjMWNcdWM3NTggXHViYzI5XHVjNzc0IFx1Yzc4OFx1YzViNFx1YzExYywgXHVkNTZkXHVjMGMxIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWJjYmRcdWM3NDQgXHVjODFjXHVhYzcwXHVkNTU4XHVjNWVjIFx1YjQ1MCBcdWJjMjlcdWM3NDQgXHVkNTY5XHVjZTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YWMwMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjQ1MCBcdWM4MTVcdWMyMTggbiwgbVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBtXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBuXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWJjYmRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmNiZFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjODE1XHViY2Y0XHViMjk0IFx1ZDU1YyBcdWM4MTVcdWMyMThcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0XHViMzcwLCBcdWMxMWNcdWNhYmRcdWM1ZDAgXHViY2JkXHVjNzc0IFx1Yzc4OFx1Yzc0NCBcdWI1NGNcdWIyOTQgMVx1Yzc0NCwgXHViZDgxXHVjYWJkXHVjNWQwIFx1YmNiZFx1Yzc3NCBcdWM3ODhcdWM3NDQgXHViNTRjXHViMjk0IDJcdWI5N2MsIFx1YjNkOVx1Y2FiZFx1YzVkMCBcdWJjYmRcdWM3NzQgXHVjNzg4XHVjNzQ0IFx1YjU0Y1x1YjI5NCA0XHViOTdjLCBcdWIwYThcdWNhYmRcdWM1ZDAgXHViY2JkXHVjNzc0IFx1Yzc4OFx1Yzc0NCBcdWI1NGNcdWIyOTQgOFx1Yzc0NCBcdWIzNTRcdWQ1NWMgXHVhYzEyXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNChcdWM3NzRcdWM5YzRcdWMyMThcdWM3NTggXHVhYzAxIFx1YmU0NFx1ZDJiOFx1Yjk3YyBcdWMwZGRcdWFjMDFcdWQ1NThcdWJhNzQgXHVjMjdkXHViMmU0KS4gXHViNTMwXHViNzdjXHVjMTFjIFx1Yzc3NCBcdWFjMTJcdWM3NDAgMFx1YmQ4MFx1ZDEzMCAxNVx1YWU0Y1x1YzljMFx1Yzc1OCBcdWJjOTRcdWM3MDQgXHVjNTQ4XHVjNWQwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwICgxKSBcdWM3NTggXHViMmY1XHVjNzQ0LCBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwICgyKSBcdWM3NTggXHViMmY1XHVjNzQ0LCBcdWMxNGJcdWM5ZjggXHVjOTA0XHVjNWQwICgzKSBcdWM3NTggXHViMmY1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyMjM0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhlIENhc3RsZSIsImRlc2NyaXB0aW9uIjoiPHByZT5cclxuICAgICAxICAgMiAgIDMgICA0ICAgNSAgIDYgICA3XHJcbiAgICMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjXHJcbiAxICMgICB8ICAgIyAgIHwgICAjICAgfCAgIHwgICAjXHJcbiAgICMjIyMjLS0tIyMjIyMtLS0jLS0tIyMjIyMtLS0jICAgXHJcbiAyICMgICAjICAgfCAgICMgICAjICAgIyAgICMgICAjXHJcbiAgICMtLS0jIyMjIy0tLSMjIyMjLS0tIyMjIyMtLS0jXHJcbiAzICMgICB8ICAgfCAgICMgICAjICAgIyAgICMgICAjICAgXHJcbiAgICMtLS0jIyMjIyMjIyMtLS0jIyMjIy0tLSMtLS0jXHJcbiA0ICMgLSZndDsjICAgfCAgIHwgICB8ICAgfCAgICMgICAjICAgXHJcbiAgICMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjICAoRmlndXJlIDEpXHJcblxyXG4jICA9IFdhbGxcclxufCAgPSBObyB3YWxsXHJcbi0gID0gTm8gd2FsbFxyXG4tJmd0OyA9IEl0IHBvaW50cyB0byB0aGUgd2FsbCB0byByZW1vdmUgYWNjb3JkaW5nIHRvIHRoZSBleGFtcGxlIG91dHB1dC48XC9wcmU+XHJcblxyXG48cD5GaWd1cmUgMSBzaG93cyB0aGUgbWFwIG9mIGEgY2FzdGxlLiBXcml0ZSBhIHByb2dyYW0gdGhhdCBjYWxjdWxhdGVzPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+aG93IG1hbnkgcm9vbXMgdGhlIGNhc3RsZSBoYXM8XC9saT5cclxuXHQ8bGk+aG93IGJpZyB0aGUgbGFyZ2VzdCByb29tIGlzPFwvbGk+XHJcblx0PGxpPndoaWNoIHdhbGwgdG8gcmVtb3ZlIGZyb20gdGhlIGNhc3RsZSB0byBtYWtlIGFzIGxhcmdlIGEgcm9vbSBhcyBwb3NzaWJsZS48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5UaGUgY2FzdGxlIGlzIGRpdmlkZWQgaW50byBtICogbiAobSZsdDs9NTAsIG4mbHQ7PTUwKSBzcXVhcmUgbW9kdWxlcy4gRWFjaCBzdWNoIG1vZHVsZSBjYW4gaGF2ZSBiZXR3ZWVuIHplcm8gYW5kIGZvdXIgd2FsbHMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgbWFwIGlzIHN0b3JlZCBpbiB0aGUgaW5wdXQgaW4gdGhlIGZvcm0gb2YgbnVtYmVycywgb25lIGZvciBlYWNoIG1vZHVsZS48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5UaGUgaW5wdXQgc3RhcnRzIHdpdGggdGhlIG51bWJlciBvZiBtb2R1bGVzIGluIHRoZSBub3J0aC1zb3V0aCBkaXJlY3Rpb24gYW5kIHRoZSBudW1iZXIgb2YgbW9kdWxlcyBpbiB0aGUgZWFzdC13ZXN0IGRpcmVjdGlvbi48XC9saT5cclxuXHQ8bGk+SW4gdGhlIGZvbGxvd2luZyBsaW5lcyBlYWNoIG1vZHVsZSBpcyBkZXNjcmliZWQgYnkgYSBudW1iZXIgKDAmbHQ7PXAmbHQ7PTE1KS4gVGhpcyBudW1iZXIgaXMgdGhlIHN1bSBvZjogMSAoPSB3YWxsIHRvIHRoZSB3ZXN0KSwgMiAoPSB3YWxsIHRvIHRoZSBub3J0aCksIDQgKD0gd2FsbCB0byB0aGUgZWFzdCksIDggKD0gd2FsbCB0byB0aGUgc291dGgpLiBJbm5lciB3YWxscyBhcmUgZGVmaW5lZCB0d2ljZTsgYSB3YWxsIHRvIHRoZSBzb3V0aCBpbiBtb2R1bGUgMSwxIGlzIGFsc28gaW5kaWNhdGVkIGFzIGEgd2FsbCB0byB0aGUgbm9ydGggaW4gbW9kdWxlIDIsMS48XC9saT5cclxuXHQ8bGk+VGhlIGNhc3RsZSBhbHdheXMgaGFzIGF0IGxlYXN0IHR3byByb29tcy48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPkluIHRoZSBvdXRwdXQsIHRoZSBmb2xsb3dpbmcgYXJlIHdyaXR0ZW4gb24gdGhyZWUgbGluZXM6IEZpcnN0IHRoZSBudW1iZXIgb2Ygcm9vbXMsIHRoZW4gdGhlIGFyZWEgb2YgdGhlIGxhcmdlc3Qgcm9vbSAoY291bnRlZCBpbiBtb2R1bGVzKSBhbmQgYSBzdWdnZXN0aW9uIG9mIHdoaWNoIHdhbGwgdG8gcmVtb3ZlIChmaXJzdCB0aGUgcm93IGFuZCB0aGVuIHRoZSBjb2x1bW4gb2YgdGhlIG1vZHVsZSBuZXh0IHRvIHRoZSB3YWxsIGFuZCBmaW5hbGx5IHRoZSBjb21wYXNzIGRpcmVjdGlvbiB0aGF0IHBvaW50cyB0byB0aGUgd2FsbCkuIEluIG91ciBleGFtcGxlICgmcXVvdDs0IDEgRSZxdW90OyBpcyBvbmUgb2Ygc2V2ZXJhbCBwb3NzaWJpbGl0aWVzLCB5b3UgbmVlZCBvbmx5IHByb2R1Y2Ugb25lKTo8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > International Olympiad in Informatics > IOI 1994 2번

  • 문제의 오타를 찾은 사람: pichulia