P16486 [GKS 2014 #C] Minesweeper

扫雷是一款在 20 世纪 80 年代流行起来的电脑游戏，至今仍被某些版本的 Microsoft Windows 操作系统收录。本题与扫雷有相似的思路，但并不假设你玩过扫雷。 在本题中，你正在一个由相同格子组成的网格上进行游戏。每个格子的内容最初是隐藏的。网格中有 $M$ 枚地雷，分别隐藏在 $M$ 个不同的格子中。其他格子均不含雷。你可以点击任意格子将其翻开。如果翻开的格子含有地雷，游戏立即结束，你输了。否则，翻开的格子会显示一个介于 $0$ 到 $8$ 之间（含两端）的数字，该数字表示其周围相邻格子中含有地雷的个数。如果两个格子共享一个角或一条边，则称它们相邻。此外，如果翻开的格子显示为 $0$，那么该格子所有相邻的格子也会被自动翻开，这一过程会递归进行。当所有不含地雷的格子都被翻开后，游戏结束，你获胜。 例如，一个初始的棋盘配置可能如下所示（“*”代表地雷，“c”是第一个被点击的格子）： ``` *..*...**. ....*..... ..c..*.... ........*. .......... ``` 被点击的格子周围没有地雷，因此它翻开后显示 $0$，并且它周围的 $8$ 个相邻格子也会被翻开。这一过程持续进行，最终得到如下棋盘： ``` *..*...**. 1112*..... 00012*.... 00001111*. 00000001.. ``` 此时，仍有一些不含雷的格子未被翻开（用 '.' 字符表示），因此玩家必须再次点击以继续游戏。 你希望尽快赢得游戏，因此想要求出赢得游戏所需的最少点击次数。给定棋盘的大小（$N \times N$），请输出这一最少点击次数。

第一行给出测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $N$。随后 $N$ 行，每行是一个长度为 $N$ 的字符串，由 '*' 和 '.' 组成，表示扫雷游戏的初始棋盘。

对于每个测试用例，输出一行形如 “Case #x: y” 的内容，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是赢得游戏所需的最少点击次数。

### 限制 $1 \le T \le 100$。 **小数据集（测试集 1 - 可见）** $1 \le N \le 50$。 **大数据集（测试集 2 - 隐藏）** $1 \le N \le 300$。 翻译由 DeepSeek V4 Pro 完成