성곽
시간 제한2초메모리 제한128 MB
벽 정보가 주어진 격자 성에서 방의 개수, 가장 큰 방의 넓이, 벽 하나를 제거해 얻을 수 있는 가장 큰 넓이를 구합니다.
문제
성곽은 M x N개의 정사각형 칸으로 이루어진 격자이다. 각 칸의 네 방향에는 벽이 있을 수 있고, 벽이 없는 방향으로만 인접한 칸으로 이동할 수 있다.
성곽의 지도가 주어질 때 다음 세 값을 구하라.
- 성곽 안에 있는 방의 개수
- 가장 넓은 방의 넓이
- 벽 하나를 제거해서 만들 수 있는 가장 넓은 방의 넓이
방의 넓이는 방을 이루는 칸의 개수이다. 성곽에는 최소 두 개의 방이 있으며, 적어도 하나의 벽을 제거해 서로 다른 두 방을 합칠 수 있다.
입력
첫째 줄에 두 정수 N, M이 주어진다. N은 가로 칸의 수, M은 세로 칸의 수이며 1 <= N, M <= 50이다.
다음 M개의 줄에는 각 줄마다 N개의 정수가 주어진다. 각 정수는 해당 칸의 벽 정보를 나타낸다. 서쪽 벽은 1, 북쪽 벽은 2, 동쪽 벽은 4, 남쪽 벽은 8을 더해서 표시한다. 따라서 각 값은 0 이상 15 이하이다.
출력
첫째 줄에 성곽 안에 있는 방의 개수를 출력한다. 둘째 줄에 가장 넓은 방의 넓이를 출력한다. 셋째 줄에 벽 하나를 제거해서 만들 수 있는 가장 넓은 방의 넓이를 출력한다.