题目描述
扫雷是一种计算机游戏,在 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
//bfs + dfs 解法
//思路可以先遍历一遍扫雷游戏的棋盘(g),创建一个二维数组d[i][j]
//二维数组d[i][j]用于记录棋盘中(i, j)位置的3 * 3连通区域内共有几颗雷
//在这个过程中还需记录有棋盘中几个位置为'*'(sum)这样也知道了最坏情况下要点击多少次
//预处理结束,开始时先开一个队列用于存储所有d[i][j] == 0的位置
//这样做是因为只有d[i][j] == 0的位置才可能减小最大的点击次数sum
//在上面这个bfs的过程中再嵌套一个dfs,因此按照题目所说(i, j)连通块内其他d[x][y] == 0的点也会被翻开
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 310;
int n;
char g[N][N];
int d[N][N];
bool st[N][N];
int dfs(int x, int y){
int res = 1;
st[x][y] = true;
for(int i = x - 1; i <= x + 1; i++)
for(int j = y - 1; j <= y + 1; j++)
if(i >= 0 && i < n && j >= 0 && j < n && !st[i][j] && g[i][j] == '.'){
if(d[i][j] == 0) res += dfs(i, j);
else{
res++;
st[i][j] = true;
}
}
return res;
}
int floodfill(){
int sum = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(g[i][j] == '*')
{
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)
d[x][y]++;
}else{
sum++;
}
queue<PII>q;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(!d[i][j]) q.push({i, j});
while(q.size()){
auto t = q.front(); q.pop();
int x = t.first, y = t.second;
if(st[x][y]) continue;
sum++;
sum -= dfs(x, y);
}
return sum;
}
int main(){
int t;
scanf("%d", &t);
for(int k = 1; k <= t; k++){
memset(st, false, sizeof st);
memset(d, 0, sizeof d);
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%s", g[i]);
int res = floodfill();
printf("Case #%d: %d\n",k, res);
}
return 0;
}
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla