题目描述

扫雷是一种计算机游戏，在20世纪80年代开始流行，并且仍然包含在某些版本的Microsoft Windows操作系统中。

在这个问题中，你正在一个矩形网格上玩扫雷游戏。

最初网格内的所有单元格都呈未打开状态。

其中M个不同的单元格中隐藏着M个地雷。

其他单元格内不包含地雷。

你可以单击任何单元格将其打开。

如果你点击到的单元格中包含一个地雷，那么游戏就会判定失败。

如果你点击到的单元格内不含地雷，则单元格内将显示一个0到8之间的数字（包括0和8），这对应于该单元格的所有相邻单元格中包含地雷的单元格的数量。

如果两个单元格共享一个角或边，则它们是相邻单元格。

另外，如果某个单元格被打开时显示数字0，那么它的所有相邻单元格也会以递归方式自动打开。

当所有不含地雷的单元格都被打开时，游戏就会判定胜利。

例如，网格的初始状态可能如下所示（’*’表示地雷，而’c’表示第一个点击的单元格）：

..….
.........
..c......
........*.
..........
被点击的单元格旁边没有地雷，因此当它被打开时显示数字0，并且它的8个相邻单元也被自动打开，此过程不断继续，最终状态如下：

..….
1112.....
00012....
00001111*.
00000001..
此时，仍有不包含地雷的单元格（用’.’字符表示）未被打开，因此玩家必须继续点击未打开的单元格，使游戏继续进行。

你想尽快赢得游戏胜利并希望找到赢得游戏的最低点击次数。

给定网格的尺寸（N×N），输出能够获胜的最小点击次数。

样例

输入样例：
2
3
..*
..*
**.
5
..*..
..*..
.*..*
.*...
.*...
输出样例：
Case #1: 2
Case #2: 8

算法

(递归、Flood Fill)

1. 记录每一个格子周围的雷的数量，如果该格子是雷，数量则为-1.同理，每个格子都会被点击一次，所以点击一次后，也标记为-1，表示不再递归该格子，也就是不在对其进行dfs()。
2. 也就是说dfs()的条件是，B[][] != -1，有2种情况， 该格子是雷，该格子被遍历过。这两种情况都不能dfs()下去。其他的，该格子如果是0，会一直遍历下去，如果不是，则会return。
3. 先计算0的数量，再计算大于0的数量。
4. 统计一个格子周围雷的数量的时候，必须是g[][] = '*的时候才res ++。之前写成了B[][] != -1，这样会漏算，会WA。

时间复杂度

C++ 代码

#include <iostream>

using namespace std;

const int N = 310;

int n, T;
int B[N][N];
char g[N][N];

void dfs(int a, int b)
{
    int t = B[a][b];
    B[a][b] = -1;
    if(t) return;
    else
    {
        for(int x = a - 1; x <= a + 1; x ++)
            for(int y = b - 1; y <= b + 1; y ++)
                if(x >= 0 && x < n && y >= 0 && y < n && B[x][y] != -1)
                    dfs(x, y);
    }
}

int main()
{
    scanf("%d", &T);
    for(int c = 1; c <= T; c ++)
    {
        int res = 0;

        scanf("%d", &n);
        for(int i = 0; i < n; i ++) scanf("%s", g[i]);

        for(int i = 0; i < n; i ++)
            for(int j = 0; j < n; j ++)
                if(g[i][j] == '*') B[i][j] = -1;
                else
                {
                    B[i][j] = 0;
                    for(int x = i - 1; x <= i + 1; x ++)
                        for(int y = j - 1; y <= j + 1; y ++)
                            if(x >= 0 && x < n && y >= 0 && y < n && g[x][y] == '*')
                                B[i][j] ++;
                }

        for(int i = 0; i < n; i ++)
            for(int j = 0; j < n; j ++)
                if(B[i][j] == 0)
                {
                    res ++;
                    dfs(i, j);
                }

        for(int i = 0; i < n; i ++)
            for(int j = 0; j < n; j ++)
                if(B[i][j] != -1)
                    res ++;

        printf("Case #%d: %d\n", c, res);
    }
}