扫雷（蓝桥杯，acwing）

题目描述：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

*..*...**.
1112*.....
00012*....
00001111*.
00000001..

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

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

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

输入格式：

第一行包含整数 T，表示共有 T 组测试数据。

每组数据第一行包含整数 N，表示游戏网格的尺寸大小。

接下来 N 行，每行包含一个长度为 N 的字符串，字符串由 .（无雷）和 *（有雷）构成，表示游戏网格的初始状态。

输出格式：

每组数据输出一个结果，每个结果占一行。

结果表示为 Case #x: y，其中 x 是组别编号（从 1 开始），y 是获胜所需的最小点击次数。

数据范围：

1≤T≤100
1≤N≤300

输入样例：

2
3
..*
..*
**.
5
..*..
..*..
.*..*
.*...
.*...

输出样例：

Case #1: 2
Case #2: 8

分析步骤：

  第一：拿到题目我们应该会比较熟悉，因为这游戏从小我们就开始玩，规则也比较简单。我们需要找到所有不是地雷的点，其中如果你点到的地方周围一圈都是没有地雷的话，那么这个点就可以向外递归，直到遍历到的点周围有地雷，就停止（就像游戏中你点到周围没有地雷的点，系统会自动显示出这一片区域的值）。我们就从这里可以知道，我们先把所有周围没有地雷的点，也就是0的点全部都点掉，那么我们就会收获绝大多数的空间，最后在遍历一遍没有被遍历的点，将他们单独点一边加上这些操作数，就可以得到最小的点击次数。

  第二：从第一步我们可以知道我们需要找到哪些是为0的点，哪些点是周围有地雷的点，哪些点是地雷点。

  第三：书写主函数，构建整体架构：

             输入值，地图。之后我们遍历一遍每一个点，如果这个点是地雷点的话，那么我们就把这个点规定为 -1（下文也是这样）;如果不是地雷的话,那么我们就先将这个点定义为0，再从这个点向外去寻找，如果这个点的周围找到了一个地雷的话我们就将这个点的数值++（数值是几，就代表周围有几个地雷）。注意是将g[i][j]++;而不是（x,y）这对坐标，因为我们去找的出发点是（i，j）; for(int x = i - 1 ; x <= i + 1 ; x ++) ； for(int y = j - 1 ; y <= j + 1 ; y++) 大家要好好理解一下，这两层for就是在这个点的上一层，这一层，下一层的周围一圈的点遍历一遍。

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

           我们将地图的每一个点都遍历一遍，知道了哪些点是0，哪些点周围有地雷，知道了这个之后，我们就先去遍历地雷数为0的点。这样操作有利于用最小的操作步数，换得尽可能多的信息，所以必须先点击地雷数为0的点。这个点是0值点就res+= ， 进入搜索

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

           遍历完这些之后，在遍历每一个点，看看有没有漏网之鱼。因为有些点周围一圈可能都是地雷，所以会点击不到，要再单独遍历一遍。没被点击的话就单独点击，res++。

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

第四：书写dfs

            我们先将t储存g的值，并将此点定义为-1（代表着地雷，也代表着不能遍历了所以一样的）。再去遍历这个点周围一圈，只要不是地雷，或者没有越界，就继续递归。

void dfs(int x , int y){int t = g[x][y];g[x][y] = -1;if(t) return ;for(int i = x - 1 ; i <= x + 1 ; i ++){for(int j = y - 1; j <= y + 1 ; j ++){if(i >= 0 and j >= 0 and i < n and j < n and g[i][j] != -1)dfs(i,j);}}
}

代码：

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 310;int g[N][N];
char str[N][N];
int m , n;void dfs(int x , int y){int t = g[x][y];g[x][y] = -1;if(t) return ;for(int i = x - 1 ; i <= x + 1 ; i ++){for(int j = y - 1; j <= y + 1 ; j ++){if(i >= 0 and j >= 0 and i < n and j < n and g[i][j] != -1)dfs(i,j);}}
}int main()
{cin>>m;for(int cases = 1 ; cases <= m ; cases ++){cin>>n;for(int i = 0 ; i < n ; i ++) cin>>str[i];for(int i = 0 ; i < n ; i ++){for(int j = 0 ; j < n ; j ++){if(str[i][j] == '*') g[i][j] = -1;else {g[i][j] = 0;for(int x = i - 1 ; x <= i + 1 ; x ++){for(int y = j - 1 ; y <= j + 1 ; y++){if(x >= 0 and y >= 0 and x < n and y < n and str[x][y] == '*')g[i][j]++;}}}}}int res = 0 ;for(int i = 0 ; i < n ; i ++){for(int j = 0 ; j < n ; j ++){if(!g[i][j]){res++;dfs(i,j);}   }}for(int i = 0 ; i < n ; i ++){for(int j = 0 ; j < n ; j ++){if(g[i][j] != -1){res++;}   }}printf("Case #%d: %d\n" , cases , res);}return 0;
}