시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 1865 706 501 36.569%

문제

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

  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
W3sicHJvYmxlbV9pZCI6IjIyMzQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxMzFcdWFjZmQiLCJkZXNjcmlwdGlvbiI6IjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMDhcL2Nhcy5QTkdcIiBzdHlsZT1cImhlaWdodDoxODlweDsgd2lkdGg6MzA3cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHViMzAwXHViN2I1IFx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YzBkZFx1YWUzNCBcdWMxMzFcdWFjZmRcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWFkNzVcdWM3NDAgXHVjMTIwXHVjNzQwIFx1YmNiZFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWFjZTAsIFx1YzgxMFx1YzEyMFx1Yzc0MCBcdWJjYmRcdWM3NzQgXHVjNWM2XHVjNWI0XHVjMTFjIFx1YzljMFx1YjA5OFx1YjJlNFx1YjJkMCBcdWMyMTggXHVjNzg4XHViMjk0IFx1ZDFiNVx1Yjg1Y1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWQ2MTVcdWQwZGNcdWM3NTggXHVjMTMxXHVjNzU4IFx1YzljMFx1YjNjNFx1Yjk3YyBcdWM3ODVcdWI4MjVcdWJjMWJcdWM1NDRcdWMxMWMgXHViMmU0XHVjNzRjXHVjNzQ0IFx1YWNjNFx1YzBiMFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlx1Yzc3NCBcdWMxMzFcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmMyOVx1Yzc1OCBcdWFjMWNcdWMyMTg8XC9saT5cclxuXHQ8bGk+XHVhYzAwXHVjN2E1IFx1YjExM1x1Yzc0MCBcdWJjMjlcdWM3NTggXHViMTEzXHVjNzc0PFwvbGk+XHJcblx0PGxpPlx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWJjYmRcdWM3NDQgXHVjODFjXHVhYzcwXHVkNTU4XHVjNWVjIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWIxMTNcdWM3NDAgXHViYzI5XHVjNzU4IFx1ZDA2Y1x1YWUzMDxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWM2MDhcdWM1ZDBcdWMxMWNcdWIyOTQgXHViYzI5XHVjNzQwIDVcdWFjMWNcdWFjZTAsIFx1YWMwMFx1YzdhNSBcdWQwNzAgXHViYzI5XHVjNzQwIDlcdWFjMWNcdWM3NTggXHVjZTc4XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM1ZDBcdWMxMWMgXHVkNjU0XHVjMGI0XHVkNDVjXHVhYzAwIFx1YWMwMFx1YjlhY1x1ZDBhNFx1YjI5NCBcdWJjYmRcdWM3NDQgXHVjODFjXHVhYzcwXHVkNTU4XHViYTc0IDE2XHVjNzc4IFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWJjMjlcdWM3NDQgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzEzMVx1Yzc0MCBtJnRpbWVzO24oMSAmbGU7IG0sIG4gJmxlOyA1MClcdWFjMWNcdWM3NTggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzEzMVx1YzVkMFx1YjI5NCBcdWNkNWNcdWMxOGMgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWJjMjlcdWM3NzQgXHVjNzg4XHVjNWI0XHVjMTFjLCBcdWQ1NmRcdWMwYzEgXHVkNTU4XHViMDk4XHVjNzU4IFx1YmNiZFx1Yzc0NCBcdWM4MWNcdWFjNzBcdWQ1NThcdWM1ZWMgXHViNDUwIFx1YmMyOVx1Yzc0NCBcdWQ1NjlcdWNlNThcdWIyOTQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViNDUwIFx1YzgxNVx1YzIxOCBuLCBtXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIG1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IG5cdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHViODVjIFx1YmNiZFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViY2JkXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM4MTVcdWJjZjRcdWIyOTQgXHVkNTVjIFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTRcdWIzNzAsIFx1YzExY1x1Y2FiZFx1YzVkMCBcdWJjYmRcdWM3NzQgXHVjNzg4XHVjNzQ0IFx1YjU0Y1x1YjI5NCAxXHVjNzQ0LCBcdWJkODFcdWNhYmRcdWM1ZDAgXHViY2JkXHVjNzc0IFx1Yzc4OFx1Yzc0NCBcdWI1NGNcdWIyOTQgMlx1Yjk3YywgXHViM2Q5XHVjYWJkXHVjNWQwIFx1YmNiZFx1Yzc3NCBcdWM3ODhcdWM3NDQgXHViNTRjXHViMjk0IDRcdWI5N2MsIFx1YjBhOFx1Y2FiZFx1YzVkMCBcdWJjYmRcdWM3NzQgXHVjNzg4XHVjNzQ0IFx1YjU0Y1x1YjI5NCA4XHVjNzQ0IFx1YjM1NFx1ZDU1YyBcdWFjMTJcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWNjMzhcdWFjZTBcdWI4NWMgXHVjNzc0XHVjOWM0XHVjMjE4XHVjNzU4IFx1YWMwMSBcdWJlNDRcdWQyYjhcdWI5N2MgXHVjMGRkXHVhYzAxXHVkNTU4XHViYTc0IFx1YzI3ZFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjIFx1Yzc3NCBcdWFjMTJcdWM3NDAgMFx1YmQ4MFx1ZDEzMCAxNVx1YWU0Y1x1YzljMFx1Yzc1OCBcdWJjOTRcdWM3MDQgXHVjNTQ4XHVjNWQwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIDFcdWM3NTggXHViMmY1XHVjNzQ0LCBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwIDJcdWM3NTggXHViMmY1XHVjNzQ0LCBcdWMxNGJcdWM5ZjggXHVjOTA0XHVjNWQwIDNcdWM3NTggXHViMmY1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyMjM0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhlIENhc3RsZSIsImRlc2NyaXB0aW9uIjoiPHByZT5cclxuICAgICAxICAgMiAgIDMgICA0ICAgNSAgIDYgICA3XHJcbiAgICMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjXHJcbiAxICMgICB8ICAgIyAgIHwgICAjICAgfCAgIHwgICAjXHJcbiAgICMjIyMjLS0tIyMjIyMtLS0jLS0tIyMjIyMtLS0jICAgXHJcbiAyICMgICAjICAgfCAgICMgICAjICAgIyAgICMgICAjXHJcbiAgICMtLS0jIyMjIy0tLSMjIyMjLS0tIyMjIyMtLS0jXHJcbiAzICMgICB8ICAgfCAgICMgICAjICAgIyAgICMgICAjICAgXHJcbiAgICMtLS0jIyMjIyMjIyMtLS0jIyMjIy0tLSMtLS0jXHJcbiA0ICMgLSZndDsjICAgfCAgIHwgICB8ICAgfCAgICMgICAjICAgXHJcbiAgICMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjICAoRmlndXJlIDEpXHJcblxyXG4jICA9IFdhbGxcclxufCAgPSBObyB3YWxsXHJcbi0gID0gTm8gd2FsbFxyXG4tJmd0OyA9IEl0IHBvaW50cyB0byB0aGUgd2FsbCB0byByZW1vdmUgYWNjb3JkaW5nIHRvIHRoZSBleGFtcGxlIG91dHB1dC48XC9wcmU+XHJcblxyXG48cD5GaWd1cmUgMSBzaG93cyB0aGUgbWFwIG9mIGEgY2FzdGxlLiBXcml0ZSBhIHByb2dyYW0gdGhhdCBjYWxjdWxhdGVzPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+aG93IG1hbnkgcm9vbXMgdGhlIGNhc3RsZSBoYXM8XC9saT5cclxuXHQ8bGk+aG93IGJpZyB0aGUgbGFyZ2VzdCByb29tIGlzPFwvbGk+XHJcblx0PGxpPndoaWNoIHdhbGwgdG8gcmVtb3ZlIGZyb20gdGhlIGNhc3RsZSB0byBtYWtlIGFzIGxhcmdlIGEgcm9vbSBhcyBwb3NzaWJsZS48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5UaGUgY2FzdGxlIGlzIGRpdmlkZWQgaW50byBtICogbiAobSZsdDs9NTAsIG4mbHQ7PTUwKSBzcXVhcmUgbW9kdWxlcy4gRWFjaCBzdWNoIG1vZHVsZSBjYW4gaGF2ZSBiZXR3ZWVuIHplcm8gYW5kIGZvdXIgd2FsbHMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgbWFwIGlzIHN0b3JlZCBpbiB0aGUgaW5wdXQgaW4gdGhlIGZvcm0gb2YgbnVtYmVycywgb25lIGZvciBlYWNoIG1vZHVsZS48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5UaGUgaW5wdXQgc3RhcnRzIHdpdGggdGhlIG51bWJlciBvZiBtb2R1bGVzIGluIHRoZSBub3J0aC1zb3V0aCBkaXJlY3Rpb24gYW5kIHRoZSBudW1iZXIgb2YgbW9kdWxlcyBpbiB0aGUgZWFzdC13ZXN0IGRpcmVjdGlvbi48XC9saT5cclxuXHQ8bGk+SW4gdGhlIGZvbGxvd2luZyBsaW5lcyBlYWNoIG1vZHVsZSBpcyBkZXNjcmliZWQgYnkgYSBudW1iZXIgKDAmbHQ7PXAmbHQ7PTE1KS4gVGhpcyBudW1iZXIgaXMgdGhlIHN1bSBvZjogMSAoPSB3YWxsIHRvIHRoZSB3ZXN0KSwgMiAoPSB3YWxsIHRvIHRoZSBub3J0aCksIDQgKD0gd2FsbCB0byB0aGUgZWFzdCksIDggKD0gd2FsbCB0byB0aGUgc291dGgpLiBJbm5lciB3YWxscyBhcmUgZGVmaW5lZCB0d2ljZTsgYSB3YWxsIHRvIHRoZSBzb3V0aCBpbiBtb2R1bGUgMSwxIGlzIGFsc28gaW5kaWNhdGVkIGFzIGEgd2FsbCB0byB0aGUgbm9ydGggaW4gbW9kdWxlIDIsMS48XC9saT5cclxuXHQ8bGk+VGhlIGNhc3RsZSBhbHdheXMgaGFzIGF0IGxlYXN0IHR3byByb29tcy48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPkluIHRoZSBvdXRwdXQsIHRoZSBmb2xsb3dpbmcgYXJlIHdyaXR0ZW4gb24gdGhyZWUgbGluZXM6IEZpcnN0IHRoZSBudW1iZXIgb2Ygcm9vbXMsIHRoZW4gdGhlIGFyZWEgb2YgdGhlIGxhcmdlc3Qgcm9vbSAoY291bnRlZCBpbiBtb2R1bGVzKSBhbmQgYSBzdWdnZXN0aW9uIG9mIHdoaWNoIHdhbGwgdG8gcmVtb3ZlIChmaXJzdCB0aGUgcm93IGFuZCB0aGVuIHRoZSBjb2x1bW4gb2YgdGhlIG1vZHVsZSBuZXh0IHRvIHRoZSB3YWxsIGFuZCBmaW5hbGx5IHRoZSBjb21wYXNzIGRpcmVjdGlvbiB0aGF0IHBvaW50cyB0byB0aGUgd2FsbCkuIEluIG91ciBleGFtcGxlICgmcXVvdDs0IDEgRSZxdW90OyBpcyBvbmUgb2Ygc2V2ZXJhbCBwb3NzaWJpbGl0aWVzLCB5b3UgbmVlZCBvbmx5IHByb2R1Y2Ugb25lKTo8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > International Olympiad in Informatics > IOI 1994 2번

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