敦化网站开发,外贸网站建站赚钱,ci策划 网站开发,wordpress动态导航题目描述#xff1a;
扫雷是一种计算机游戏#xff0c;在 2020 世纪 80 年代开始流行#xff0c;并且仍然包含在某些版本的 Microsoft Windows 操作系统中。
在这个问题中#xff0c;你正在一个矩形网格上玩扫雷游戏。
最初网格内的所有单元格都呈未打开状态。
其中 M个…题目描述
扫雷是一种计算机游戏在 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这对坐标因为我们去找的出发点是ij; 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 algorithmusing 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()
{cinm;for(int cases 1 ; cases m ; cases ){cinn;for(int i 0 ; i n ; i ) cinstr[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;
}
