데이터 마이닝?

거의 모든 컴퓨터 플랫폼에는 지뢰 찾기 게임의 변형이 존재합니다. 당신의 고용주는 전문가가 아니라 가벼운 사용자를 위한 또 다른 버전을 만들고자 합니다. 당신이 할 일은, 지뢰 찾기 판을 입력받아 가벼운 사용자가 최선을 다한 뒤에도 여전히 덮여 있는 지뢰가 아닌 칸의 최소 개수를 구하는 프로그램을 작성하는 것입니다. 게임 규칙과 요구 동작은 아래에 설명되어 있습니다.

지뢰 찾기 판은 칸들로 이루어진 직사각형 격자이며, 하나 이상의 칸에 지뢰가 들어 있습니다. 처음에는 모든 칸이 덮여(빈 상태로) 있습니다. 목표는 지뢰가 없는 모든 칸을 여는 것입니다. 지뢰가 열리면 게임이 끝나고 플레이어는 패배합니다. 각 칸은 덮힘, 열림, 지뢰로 표시됨(깃발) 중 하나의 상태를 가집니다.

지뢰가 없는 칸을 열면, 그 칸에는 인접한 칸에 있는 지뢰의 개수가 표시됩니다. 이 숫자는 플레이어가 지뢰의 위치를 파악하는 데 도움이 됩니다. 인접한 칸이란 열린 칸을 중심으로 하는 $3 \times 3$ 정사각형을 이루는 칸들이며, 위치에 따라 한 칸의 인접 칸은 3개에서 8개까지입니다. 아래 그림 1에서는 $(3,1)$과 $(3,2)$에 지뢰 두 개가 있고, 나머지 각 칸에는 인접한 지뢰의 개수가 표시되어 있습니다.

가벼운 사용자는 이 정보를 다음과 같이 활용합니다. 먼저 완전히 덮여 있는 판에서 칸 하나를 고릅니다. 그 칸이 지뢰이면 게임이 끝납니다. 그렇지 않으면 그 칸을 열고, 더 이상 진행할 수 없을 때까지 열린 칸들에 아래 두 규칙을 반복해서 적용합니다. 열린 칸의 위치를 $(x,y)$라 하고, $(x,y)$에 인접한 깃발이 꽂힌 칸, 덮인 칸, 지뢰 칸의 개수를 각각 $f$, $c$, $m$이라 합시다.

1. $f = m$이면, $(x,y)$에 인접한 모든 덮인 칸을 엽니다.
2. $f + c = m$이면, $(x,y)$에 인접한 모든 덮인 칸에 깃발을 꽂습니다.

첫 칸을 성공적으로 연 뒤, 가벼운 사용자는 규칙 1이나 규칙 2가 지시하는 경우를 제외하고는 절대 칸을 열거나 깃발을 꽂지 않으므로 막힐 수 있습니다. 가벼운 사용자가 막히면 게임이 끝납니다. 더 이상 추측하지 않으며, 추가로 칸을 안전하게 열 수 있을지도 모르는 더 복잡한 추론은 사용하지 않습니다.

그림 2는 그림 1의 판에 이 규칙들을 적용하는 과정을 보여 줍니다. 그림 2a는 플레이어가 처음에 $(1,2)$ 칸을 연 뒤의 판입니다. 규칙 1이 적용되어(깃발 0개 $=$ 인접 지뢰 0개), 인접한 $(1,1)$, $(1,3)$, $(2,1)$, $(2,2)$, $(2,3)$ 칸을 열어 그림 2b가 됩니다. 그림 2b에서 플레이어는 $(2,1)$ 칸을 보고 규칙 2를 적용하여(깃발 0개 $+$ 덮인 칸 2개 $=$ 지뢰 2개), $(3,1)$과 $(3,2)$ 칸에 깃발을 꽂아 그림 2c가 됩니다. 마지막으로 $(2,3)$ 칸을 보면, $(2,3)$은 인접 지뢰가 정확히 1개이고 $(3,2)$ 칸에는 이미 깃발이 꽂혀 있으므로, 규칙 1을 다시 적용하여 $(3,3)$ 칸을 엽니다. 이제 지뢰가 없는 모든 칸이 열렸으므로 게임은 플레이어의 승리로 끝납니다(그림 2d).

앞서 말했듯이 이 두 규칙만으로는 모든 시작 칸에서 모든 판을 풀 수 없으므로 플레이어는 막힐 수 있습니다. 다시 그림 1의 판에서, 플레이어가 처음에 $(2,2)$ 칸을 열면 판은 그림 3이 됩니다. 규칙 1도 규칙 2도 새로운 칸을 열거나 깃발을 꽂지 않으므로 더 이상 진행할 수 없고, 플레이어는 지뢰가 없는 덮인 칸 6개가 남은 채로 막힙니다.

당신의 프로그램은 판을 살펴, 가벼운 사용자가 위와 같이 플레이할 때 남을 수 있는 지뢰가 아닌 덮인 칸의 최소 개수를 구해야 합니다. 그림 1의 판에서는 정답이 0입니다.

그림 1	그림 2a	그림 2b	그림 2c	그림 2d	그림 3

입력은 하나 이상의 판으로 이루어지며, 마지막에는 두 개의 0만 담긴 줄이 옵니다. 각 판은 두 정수 $r$과 $c$가 담긴 줄로 시작하며, 각각 행과 열의 수입니다. $r$과 $c$는 항상 3 이상이고, 한 판의 전체 칸 수는 40을 넘지 않습니다. 이어지는 $r$개의 줄이 판 자체를 나타내며, 대문자 M은 지뢰, 마침표 .는 빈 칸입니다. 모든 판에는 M이 적어도 하나, .이 적어도 하나 있습니다.

각 판마다, 그 판에서 남을 수 있는 지뢰가 아닌 덮인 칸의 최소 개수를 정수 하나로 한 줄에 출력하세요.