Data Mining?

A variation of the Minesweeper game exists for almost every computer platform. Your employer wants to build yet another version, this one aimed at casual players rather than experts. Your task is to write a program that takes a Minesweeper board and reports the minimum number of covered, unmined cells that can remain after a casual player has done his or her best. The rules of the game and the required behavior are described below.

A Minesweeper board is a rectangular grid of cells, one or more of which contain a mine. At the start every cell is covered (blank). The goal is to uncover every cell that does not contain a mine. If a mine is uncovered, the game ends and the player loses. Each cell is in one of three states: covered, cleared (uncovered), or flagged as a mine.

When a player clears a cell that does not contain a mine, that cell shows the number of mines among the cells adjacent to it. These numbers help the player locate the mines. The adjacent cells are the cells that form a $3 \times 3$ square centered on the cleared cell, so depending on its position a cell has between 3 and 8 neighbors. In Figure 1 below, two mines sit at $(3,1)$ and $(3,2)$, and every other cell shows its count of adjacent mines.

A casual player uses this information as follows. First the player picks one cell on a fully covered board. If it is a mine, the game is over. Otherwise the player clears that cell and then repeatedly applies the two rules below to cleared cells until no further progress is possible. Let $(x,y)$ be the location of a cleared cell, and let $f$, $c$, and $m$ be the number of flagged, covered, and mined cells adjacent to $(x,y)$.

1. If $f = m$, clear every covered cell adjacent to $(x,y)$.
2. If $f + c = m$, flag every covered cell adjacent to $(x,y)$.

After successfully clearing the first cell, a casual player never clears or flags a cell except as dictated by rule 1 or rule 2, so the player may get stuck. When a casual player is stuck the game ends: no further guesses are made, and the player does not use any more advanced reasoning that might safely clear additional cells.

Figure 2 shows these rules applied to the board from Figure 1. Figure 2a shows the board after the player first clears cell $(1,2)$. Rule 1 applies (0 flagged $=$ 0 mined neighbors), so the player clears the adjacent cells $(1,1)$, $(1,3)$, $(2,1)$, $(2,2)$, and $(2,3)$, giving Figure 2b. From Figure 2b the player looks at cell $(2,1)$ and applies rule 2 (0 flagged $+$ 2 covered $=$ 2 mined) to flag cells $(3,1)$ and $(3,2)$ as mines, giving Figure 2c. Finally, looking at cell $(2,3)$, the player applies rule 1 again to clear cell $(3,3)$, because $(2,3)$ has exactly one adjacent mine and cell $(3,2)$ is already flagged. Now every mine-free cell has been cleared, so the game ends with the player winning (Figure 2d).

As noted, these two rules are not enough to solve every board from every starting cell, so the player may get stuck. Using the board of Figure 1 again, if the player instead first clears cell $(2,2)$, the board becomes Figure 3. No further progress is possible, since neither rule 1 nor rule 2 clears or flags any new cell, and the player is stuck with 6 covered, mine-free cells.

Your program must examine a board and determine the smallest number of covered, unmined cells that could remain when a casual player plays as described. For the board in Figure 1 the answer is 0.

Figure 1	Figure 2a	Figure 2b	Figure 2c	Figure 2d	Figure 3

The input contains one or more boards, followed by a final line containing only two zeros. Each board begins with a line holding two integers $r$ and $c$: the number of rows and columns. Both $r$ and $c$ are always at least 3, and the total number of cells on any board is never greater than 40. The next $r$ lines give the board itself, where an uppercase M is a mine and a period . is an empty cell. Every board contains at least one M and at least one ..

For each board, print one line containing a single integer: the smallest number of covered, unmined cells that can remain for that board.