시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB112115464389147.556%

문제

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

  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+XHJcblx0PGxpPlx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWJjYmRcdWM3NDQgXHVjODFjXHVhYzcwXHVkNTU4XHVjNWVjIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWIxMTNcdWM3NDAgXHViYzI5XHVjNzU4IFx1ZDA2Y1x1YWUzMDxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWM2MDhcdWM1ZDBcdWMxMWNcdWIyOTQgXHViYzI5XHVjNzQwIDVcdWFjMWNcdWFjZTAsIFx1YWMwMFx1YzdhNSBcdWQwNzAgXHViYzI5XHVjNzQwIDlcdWFjMWNcdWM3NTggXHVjZTc4XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM1ZDBcdWMxMWMgXHVkNjU0XHVjMGI0XHVkNDVjXHVhYzAwIFx1YWMwMFx1YjlhY1x1ZDBhNFx1YjI5NCBcdWJjYmRcdWM3NDQgXHVjODFjXHVhYzcwXHVkNTU4XHViYTc0IDE2XHVjNzc4IFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWJjMjlcdWM3NDQgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzEzMVx1Yzc0MCBNICZ0aW1lczsgTigxICZsZTsgTSwgTiAmbGU7IDUwKVx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHVjZTc4XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNFx1YjJlNC4gXHVjMTMxXHVjNWQwXHViMjk0IFx1Y2Q1Y1x1YzE4YyBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YmMyOVx1Yzc3NCBcdWM3ODhcdWM1YjRcdWMxMWMsIFx1ZDU2ZFx1YzBjMSBcdWQ1NThcdWIwOThcdWM3NTggXHViY2JkXHVjNzQ0IFx1YzgxY1x1YWM3MFx1ZDU1OFx1YzVlYyBcdWI0NTAgXHViYzI5XHVjNzQ0IFx1ZDU2OVx1Y2U1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWI0NTAgXHVjODE1XHVjMjE4IE4sIE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWI4NWMgXHViY2JkXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJjYmRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzgxNVx1YmNmNFx1YjI5NCBcdWQ1NWMgXHVjODE1XHVjMjE4XHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NFx1YjM3MCwgXHVjMTFjXHVjYWJkXHVjNWQwIFx1YmNiZFx1Yzc3NCBcdWM3ODhcdWM3NDQgXHViNTRjXHViMjk0IDFcdWM3NDQsIFx1YmQ4MVx1Y2FiZFx1YzVkMCBcdWJjYmRcdWM3NzQgXHVjNzg4XHVjNzQ0IFx1YjU0Y1x1YjI5NCAyXHViOTdjLCBcdWIzZDlcdWNhYmRcdWM1ZDAgXHViY2JkXHVjNzc0IFx1Yzc4OFx1Yzc0NCBcdWI1NGNcdWIyOTQgNFx1Yjk3YywgXHViMGE4XHVjYWJkXHVjNWQwIFx1YmNiZFx1Yzc3NCBcdWM3ODhcdWM3NDQgXHViNTRjXHViMjk0IDhcdWM3NDQgXHViMzU0XHVkNTVjIFx1YWMxMlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Y2MzOFx1YWNlMFx1Yjg1YyBcdWM3NzRcdWM5YzRcdWMyMThcdWM3NTggXHVhYzAxIFx1YmU0NFx1ZDJiOFx1Yjk3YyBcdWMwZGRcdWFjMDFcdWQ1NThcdWJhNzQgXHVjMjdkXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMgXHVjNzc0IFx1YWMxMlx1Yzc0MCAwXHViZDgwXHVkMTMwIDE1XHVhZTRjXHVjOWMwXHVjNzU4IFx1YmM5NFx1YzcwNCBcdWM1NDhcdWM1ZDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgMVx1Yzc1OCBcdWIyZjVcdWM3NDQsIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDAgMlx1Yzc1OCBcdWIyZjVcdWM3NDQsIFx1YzE0Ylx1YzlmOCBcdWM5MDRcdWM1ZDAgM1x1Yzc1OCBcdWIyZjVcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjIyMzQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUaGUgQ2FzdGxlIiwiZGVzY3JpcHRpb24iOiI8cHJlPlxyXG4gICAgIDEgICAyICAgMyAgIDQgICA1ICAgNiAgIDdcclxuICAgIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyNcclxuIDEgIyAgIHwgICAjICAgfCAgICMgICB8ICAgfCAgICNcclxuICAgIyMjIyMtLS0jIyMjIy0tLSMtLS0jIyMjIy0tLSMgICBcclxuIDIgIyAgICMgICB8ICAgIyAgICMgICAjICAgIyAgICNcclxuICAgIy0tLSMjIyMjLS0tIyMjIyMtLS0jIyMjIy0tLSNcclxuIDMgIyAgIHwgICB8ICAgIyAgICMgICAjICAgIyAgICMgICBcclxuICAgIy0tLSMjIyMjIyMjIy0tLSMjIyMjLS0tIy0tLSNcclxuIDQgIyAtJmd0OyMgICB8ICAgfCAgIHwgICB8ICAgIyAgICMgICBcclxuICAgIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMgIChGaWd1cmUgMSlcclxuXHJcbiMgID0gV2FsbFxyXG58ICA9IE5vIHdhbGxcclxuLSAgPSBObyB3YWxsXHJcbi0mZ3Q7ID0gSXQgcG9pbnRzIHRvIHRoZSB3YWxsIHRvIHJlbW92ZSBhY2NvcmRpbmcgdG8gdGhlIGV4YW1wbGUgb3V0cHV0LjxcL3ByZT5cclxuXHJcbjxwPkZpZ3VyZSAxIHNob3dzIHRoZSBtYXAgb2YgYSBjYXN0bGUuIFdyaXRlIGEgcHJvZ3JhbSB0aGF0IGNhbGN1bGF0ZXM8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5ob3cgbWFueSByb29tcyB0aGUgY2FzdGxlIGhhczxcL2xpPlxyXG5cdDxsaT5ob3cgYmlnIHRoZSBsYXJnZXN0IHJvb20gaXM8XC9saT5cclxuXHQ8bGk+d2hpY2ggd2FsbCB0byByZW1vdmUgZnJvbSB0aGUgY2FzdGxlIHRvIG1ha2UgYXMgbGFyZ2UgYSByb29tIGFzIHBvc3NpYmxlLjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlRoZSBjYXN0bGUgaXMgZGl2aWRlZCBpbnRvIG0gKiBuIChtJmx0Oz01MCwgbiZsdDs9NTApIHNxdWFyZSBtb2R1bGVzLiBFYWNoIHN1Y2ggbW9kdWxlIGNhbiBoYXZlIGJldHdlZW4gemVybyBhbmQgZm91ciB3YWxscy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBtYXAgaXMgc3RvcmVkIGluIHRoZSBpbnB1dCBpbiB0aGUgZm9ybSBvZiBudW1iZXJzLCBvbmUgZm9yIGVhY2ggbW9kdWxlLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlRoZSBpbnB1dCBzdGFydHMgd2l0aCB0aGUgbnVtYmVyIG9mIG1vZHVsZXMgaW4gdGhlIG5vcnRoLXNvdXRoIGRpcmVjdGlvbiBhbmQgdGhlIG51bWJlciBvZiBtb2R1bGVzIGluIHRoZSBlYXN0LXdlc3QgZGlyZWN0aW9uLjxcL2xpPlxyXG5cdDxsaT5JbiB0aGUgZm9sbG93aW5nIGxpbmVzIGVhY2ggbW9kdWxlIGlzIGRlc2NyaWJlZCBieSBhIG51bWJlciAoMCZsdDs9cCZsdDs9MTUpLiBUaGlzIG51bWJlciBpcyB0aGUgc3VtIG9mOiAxICg9IHdhbGwgdG8gdGhlIHdlc3QpLCAyICg9IHdhbGwgdG8gdGhlIG5vcnRoKSwgNCAoPSB3YWxsIHRvIHRoZSBlYXN0KSwgOCAoPSB3YWxsIHRvIHRoZSBzb3V0aCkuIElubmVyIHdhbGxzIGFyZSBkZWZpbmVkIHR3aWNlOyBhIHdhbGwgdG8gdGhlIHNvdXRoIGluIG1vZHVsZSAxLDEgaXMgYWxzbyBpbmRpY2F0ZWQgYXMgYSB3YWxsIHRvIHRoZSBub3J0aCBpbiBtb2R1bGUgMiwxLjxcL2xpPlxyXG5cdDxsaT5UaGUgY2FzdGxlIGFsd2F5cyBoYXMgYXQgbGVhc3QgdHdvIHJvb21zLjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+SW4gdGhlIG91dHB1dCwgdGhlIGZvbGxvd2luZyBhcmUgd3JpdHRlbiBvbiB0aHJlZSBsaW5lczogRmlyc3QgdGhlIG51bWJlciBvZiByb29tcywgdGhlbiB0aGUgYXJlYSBvZiB0aGUgbGFyZ2VzdCByb29tIChjb3VudGVkIGluIG1vZHVsZXMpIGFuZCBhIHN1Z2dlc3Rpb24gb2Ygd2hpY2ggd2FsbCB0byByZW1vdmUgKGZpcnN0IHRoZSByb3cgYW5kIHRoZW4gdGhlIGNvbHVtbiBvZiB0aGUgbW9kdWxlIG5leHQgdG8gdGhlIHdhbGwgYW5kIGZpbmFsbHkgdGhlIGNvbXBhc3MgZGlyZWN0aW9uIHRoYXQgcG9pbnRzIHRvIHRoZSB3YWxsKS4gSW4gb3VyIGV4YW1wbGUgKCZxdW90OzQgMSBFJnF1b3Q7IGlzIG9uZSBvZiBzZXZlcmFsIHBvc3NpYmlsaXRpZXMsIHlvdSBuZWVkIG9ubHkgcHJvZHVjZSBvbmUpOjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > International Olympiad in Informatics > IOI 1994 > Day 1 2번