题目描述
扫雷是一种计算机游戏,在 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
难度:简单
时/空限制:1s / 64MB
来源:
Google Kickstart2014 Round C Problem A
算法标签
C++
算法1
(bfs) $O(n^2)$
C++ 代码
#include<cstdio>
#include<cstring>
#include<iostream>
#define x first
#define y second
using namespace std;
const int N=310;
typedef pair<int,int>PII;
char str[N][N];
int g[N][N];
int n;
int dx[8]={-1,-1,-1,0,1,1,1,0},dy[8]={-1,0,1,1,1,0,-1,-1};
PII q[N*N];
void bfs(int a,int b)
{
int hh=0,tt=0;
q[0]={a,b};
g[a][b]=-1;
while(hh<=tt)
{
auto t=q[hh++];
for(int i=0;i<8;i++)
{
int x=t.x+dx[i],y=t.y+dy[i];
if(x>=0&&x<n&&y>=0&&y<n&&g[x][y]!=-1)
{
if(g[x][y]==0)
q[++tt]={x,y};
g[x][y]=-1;
}
}
}
}
int main()
{
int T;scanf("%d",&T);
for(int t=1;t<=T;t++)
{
scanf("%d",&n);
memset(g,0,sizeof g);
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 if(str[i][j]=='.')
{
for(int m=0;m<8;m++)
{
int x=i+dx[m],y=j+dy[m];
if(x>=0&&x<n&&y>=0&&y<n&&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 ++ ;
bfs(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",t,res);
printf("\n");
}
return 0;
}
算法2
(dfs) $O(n^2)$
C++ 代码
#include<cstdio>
#include<cstring>
const int N=310;
char str[N][N];
int g[N][N];
int n;
int dx[8]={-1,-1,-1,0,1,1,1,0},dy[8]={-1,0,1,1,1,0,-1,-1};
void dfs(int a,int b)
{
int t=g[a][b];
g[a][b]=-1;
if(t) return;
for(int i=0;i<8;i++)
{
int x=a+dx[i],y=b+dy[i];
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 t=1;t<=T;t++)
{
scanf("%d",&n);
memset(g,0,sizeof g);
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 if(str[i][j]=='.')
{
for(int m=0;m<8;m++)
{
int x=i+dx[m],y=j+dy[m];
if(x>=0&&x<n&&y>=0&&y<n&&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",t,res);
printf("\n");
}
return 0;
}