시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 751 268 187 34.953%

문제

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

(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) 의 답을 출력한다.

예제 입력

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

예제 출력

5
9
16

힌트

출처

Olympiad > International Olympiad in Informatics > IOI 1994 2번

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