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

本文主要是介绍【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点一遍

  1. 点一遍每个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;
}

这篇关于【AcWing】蓝桥杯集训每日一题Day14|Flood Fill|洪水灌溉算法|DFS|并查集|687.扫雷(C++)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/887279

相关文章

Windows下C++使用SQLitede的操作过程

《Windows下C++使用SQLitede的操作过程》本文介绍了Windows下C++使用SQLite的安装配置、CppSQLite库封装优势、核心功能(如数据库连接、事务管理)、跨平台支持及性能优... 目录Windows下C++使用SQLite1、安装2、代码示例CppSQLite:C++轻松操作SQ

C++中RAII资源获取即初始化

《C++中RAII资源获取即初始化》RAII通过构造/析构自动管理资源生命周期,确保安全释放,本文就来介绍一下C++中的RAII技术及其应用,具有一定的参考价值,感兴趣的可以了解一下... 目录一、核心原理与机制二、标准库中的RAII实现三、自定义RAII类设计原则四、常见应用场景1. 内存管理2. 文件操

C++中零拷贝的多种实现方式

《C++中零拷贝的多种实现方式》本文主要介绍了C++中零拷贝的实现示例,旨在在减少数据在内存中的不必要复制,从而提高程序性能、降低内存使用并减少CPU消耗,零拷贝技术通过多种方式实现,下面就来了解一下... 目录一、C++中零拷贝技术的核心概念二、std::string_view 简介三、std::stri

C++高效内存池实现减少动态分配开销的解决方案

《C++高效内存池实现减少动态分配开销的解决方案》C++动态内存分配存在系统调用开销、碎片化和锁竞争等性能问题,内存池通过预分配、分块管理和缓存复用解决这些问题,下面就来了解一下... 目录一、C++内存分配的性能挑战二、内存池技术的核心原理三、主流内存池实现:TCMalloc与Jemalloc1. TCM

C++ 函数 strftime 和时间格式示例详解

《C++函数strftime和时间格式示例详解》strftime是C/C++标准库中用于格式化日期和时间的函数,定义在ctime头文件中,它将tm结构体中的时间信息转换为指定格式的字符串,是处理... 目录C++ 函数 strftipythonme 详解一、函数原型二、功能描述三、格式字符串说明四、返回值五

C++作用域和标识符查找规则详解

《C++作用域和标识符查找规则详解》在C++中,作用域(Scope)和标识符查找(IdentifierLookup)是理解代码行为的重要概念,本文将详细介绍这些规则,并通过实例来说明它们的工作原理,需... 目录作用域标识符查找规则1. 普通查找(Ordinary Lookup)2. 限定查找(Qualif

C/C++ chrono简单使用场景示例详解

《C/C++chrono简单使用场景示例详解》:本文主要介绍C/C++chrono简单使用场景示例详解,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友... 目录chrono使用场景举例1 输出格式化字符串chrono使用场景China编程举例1 输出格式化字符串示

C++/类与对象/默认成员函数@构造函数的用法

《C++/类与对象/默认成员函数@构造函数的用法》:本文主要介绍C++/类与对象/默认成员函数@构造函数的用法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录名词概念默认成员函数构造函数概念函数特征显示构造函数隐式构造函数总结名词概念默认构造函数:不用传参就可以

C++类和对象之默认成员函数的使用解读

《C++类和对象之默认成员函数的使用解读》:本文主要介绍C++类和对象之默认成员函数的使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、默认成员函数有哪些二、各默认成员函数详解默认构造函数析构函数拷贝构造函数拷贝赋值运算符三、默认成员函数的注意事项总结一

C/C++中OpenCV 矩阵运算的实现

《C/C++中OpenCV矩阵运算的实现》本文主要介绍了C/C++中OpenCV矩阵运算的实现,包括基本算术运算(标量与矩阵)、矩阵乘法、转置、逆矩阵、行列式、迹、范数等操作,感兴趣的可以了解一下... 目录矩阵的创建与初始化创建矩阵访问矩阵元素基本的算术运算 ➕➖✖️➗矩阵与标量运算矩阵与矩阵运算 (逐元