A variation of the minesweeper game is available for almost every computer platform. Your employer wants to create yet another version that is targeted toward casual, as opposed to expert, players. Your task is to write a program that takes a minesweeper board and returns the minimum number of covered, unmined cells that remain after a casual player has tried his/her best. The details of the game and program are decribed below.
A minesweeper board consists of a rectangular grid of cells, with one or more cells containing a mine. The entire board is initially presented with all the cells covered, i.e., blank. The object of the game is to uncover all the cells that do not contain a mine. If a mine in uncovered, the game is over and the player loses. A cell can be in one of 3 states: covered, cleared/uncovered, or flagged as a mine.
When a player clears a cell that does not contain a mine, that cell displays the number of mines in cells that are adjacent to it. These numbers help the player determine where the mines are located. The adjacent cells are the cells that form a 3x3 square with the cleared cell in the center. Depending on a cell's location, it will have between 3 and 8 adjacent cells. The board in Figure 1 below shows two mines at locations (3,1) and (3,2), and the numbers of adjacent mines for each of the remaining cells.
A casual player makes use of this information in the following way. First the player selects one cell from a totally covered board. If it's a mine, the game is over. Otherwise, the player clears the cell and then applies the following two rules to cleared cells on the board until no further progress can be made. 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).
The input contains one or more game boards, followed by a final line containing only two zeros. A game board starts with a line containing two integers, r and c, the number of rows and columns in the game board; r and c will always be at least 3. The total number of cells in any board will never be greater than 40. The rest of the data set consists of a graphical representation of the game board, where an upper case 'M' represents a mine and a period '.' represents an empty cell. There will always be at least one 'M' and at least one '.' on each game board.
For each data set write one line with a single integer indicating the smallest number of covered, unmined cells for that board.
3 3 ... ... MM. 3 4 M.M. .M.M M.M. 7 5 ..... ..... MMM.. M.M.. MMM.. ..... ..... 4 4 ...M .... .... M... 0 0
0 5 1 0