Minimum Clicks in Minesweeper

Minesweeper is a computer game that became popular in the 1980s. This problem uses the same rules, but you do not need to have played it.

You play on an $N \times N$ grid of identical cells. Every cell is hidden at the start. Mines are hidden in $M$ different cells, one mine per cell, and no other cell holds a mine. You may click any cell to reveal it. If the revealed cell holds a mine, you lose. Otherwise the revealed cell shows a digit from 0 to 8, the number of neighboring cells that hold mines. Two cells are neighbors when they share an edge or a corner. If the revealed cell shows 0, all of its neighbors are revealed too, and the same rule applies again to each newly revealed cell. You win once every cell without a mine is revealed.

For example, suppose the board starts like this, where * is a mine and c is the first clicked cell.

*..*..
......
..c...
.....*
......
.*....

No mine neighbors the clicked cell, so that cell becomes a 0 and its eight neighbors are revealed with it. The rule keeps applying and the board turns into this.

*..*..
11111.
00001.
00001*
111011
.*1000

Cells without a mine are still hidden, shown as ., so the player has to click again to finish the game.

You want to win with as few clicks as possible. Assuming you never click a mine, find the minimum number of clicks needed to win. If every cell holds a mine, there is nothing left to reveal and you have already won, so the answer is 0.

The first line contains the number of test cases, $T$.

The first line of each test case contains the board size $N$. The next $N$ lines each contain a string of length $N$ describing the initial board. Each string consists of * and . only, where * is a cell with a mine and . is a cell without one.

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the minimum number of clicks needed to win.

• $1 \le T \le 100$
• $1 \le N \le 300$