【AcWing】蓝桥杯集训每日一题Day14|Flood Fill|洪水灌溉算法|DFS|并查集|687.扫雷(C++)

687.扫雷

687. 扫雷 - AcWing题库
难度：简单
时/空限制：1s / 64MB
总通过数：2865
总尝试数：5315
来源： Google Kickstart2014 Round C Problem A
算法标签 BFSDFSFlood Fill

题目内容

扫雷是一种计算机游戏，在 20 世纪 80 年代开始流行，并且仍然包含在某些版本的 Microsoft Windows 操作系统中。
在这个问题中，你正在一个矩形网格上玩扫雷游戏。
最初网格内的所有单元格都呈未打开状态。
其中 M 个不同的单元格中隐藏着 M 个地雷。
其他单元格内不包含地雷。
你可以单击任何单元格将其打开。
如果你点击到的单元格中包含一个地雷，那么游戏就会判定失败。
如果你点击到的单元格内不含地雷，则单元格内将显示一个 0 到 8 之间的数字（包括 0 和 8），这对应于该单元格的所有相邻单元格中包含地雷的单元格的数量。
如果两个单元格共享一个角或边，则它们是相邻单元格。
另外，如果某个单元格被打开时显示数字 0，那么它的所有相邻单元格也会以递归方式自动打开。
当所有不含地雷的单元格都被打开时，游戏就会判定胜利。
例如，网格的初始状态可能如下所示（* 表示地雷，而 c 表示第一个点击的单元格）：

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

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

*..*...**.
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

题目详解

上帝视角下，最少点多少下，可以把所有的空地点开
N最大是300，也就是最多有300的平方90000个格子，一共有100个数据，整个数据量不到1000万
把时间复杂度控制在线性阶

点的这个位置如果是0的话，周围只要有0，就会递归式地全部展开
可以先看所有0的连通块有哪些
块与块之间是相互独立的
每一块内只要点任意一个，就会单独展开
如果不点块内的0的话，它就一定不会被展开，因为这一块周围已经没有0了
因此每一个0的连通块都要点一下，它才可以展开

考虑最小值的时候，因为所有方案都要把所有0全部点一遍，所以第一步可以先把所有0点一遍

点一遍每个0的连通块
剩余的元素肯定不是0了，是1~8的数字

如果一个元素周围8个没有0的话，就一定要点一下，不点的话，就一定不会展开，
2. 其余的1~8，如果周围没有0，就必须要点
3. 剩余的1~8，周围有0的话，有可能点有可能不点，取决于点的顺序
1. 如果是先点其他的，再点0，就需要点一下
2. 如果是先点0，就会把周围一圈直接相邻的不是0的一块展开，不需要点
3. 由于求的是最小值，所以一定是先点0，再点1~8，就不需要点了
答案就是0的连通块的数量+加上周围没有0的1~8的数量

Flood Fill算法

洪水灌溉算法
可以把扫雷中空白的格看作是洼地，周围的1是山峰，可以看成是在格子这块开始注水，注完之后会把所有的洼地填满

实现方式可以用DFS或BFS
一般使用DFS，因为代码比较短

也可以使用并查集

所有八方向相连，有公共边相连，有公共点也算相连
只要在周围的八个方向上都是0的话，就可以建一条边，就可以用并查集合并到一个集合里，就可以用并查集维护出来所有0的连通块的数量
再统计一下1~8周围无0的数量，就可以了

代码

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 310;
//N最大等于300int n;
//存储矩阵
char str[N][N];
int g[N][N];   //存储周围每个格子的数量，-1表示本身是雷//FloodFill算法
void dfs(int a, int b)
{int t = g[a][b];//每遍历一个，给标记一下g[a][b] = -1;//如果发现这个位置不是0，也就是扩展到边界了，就不要继续拓展了if (t) return;//枚举一下a和b周围的8个方向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 && g[x][y] != -1)dfs(x, y);	
}int main()
{//读入一下测试数据的数量int T;scanf("%d", &T);//依次读入每一个测试数据for (int cases = 1; cases <= T; cases ++){//读入边的长度scanf("%d", &n);//依次读入整个地图for (int i = 0; i < n; i ++) scanf("%s", 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 && x < n && y >= 0 && y < n && str[x][y] == '*')g[i][j] ++;}int res = 0;//依次枚举一下所有没有被处理过的0for (int i = 0; i < n; i ++)for (int j = 0; j < n; j ++)//如果当前的位置是0的话if (!g[i][j]){res ++;//从当前点做一个FloodFill，把所有相邻的0都标记一下dfs(i, j);}//统计一下所有剩余的1~8的数量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;
}