AcWing 687. 扫雷
原题链接
简单
作者:
liebe_1
,
2024-04-08 13:26:12
,
所有人可见
,
阅读 10
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 320;
int n;
char g[N][N];//棋盘字符
int p[N][N];//每个棋子的八个方向总的地雷数量
void dfs(int a, int b) {
int t = p[a][b];//记下当前棋子周围地雷的数量
p[a][b] = -1;//遍历过了,消除棋子
if(t)return ;//假如当前棋子不是0,那么就不往下遍历了
for(int x = a-1; x <= a+1; x++) {
for(int y = b-1; y <= b+1; y++) {//八方找0棋子
if(x>=0 && x<n && y>=0 && y<n && p[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",g[i]);//输入棋盘
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(g[i][j] == '*')p[i][j] = -1;//假如是雷就设为-1;
else {
p[i][j] = 0;//周围雷的数量初始化为0
for(int x = i-1; x <= i+1; x++)
for(int y = j-1; y <= j+1; y++)//八方寻找雷
if(g[x][y] == '*'&& x>=0 && x<n && y>= 0&& y<n)p[i][j]++;
}
}
}
int res = 0;
//先找零连通图,有几个就要点几次
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(p[i][j] == 0) {
res++;
dfs(i,j);
}
}
}
//已经将附近有零或本身是零的棋子全部变成了-1
//再找1-8附近没有零的棋子,这样的每一个棋子都要一次点击
for(int i = 0; i < n; i++) {
for(int j = 0; j < n ;j++) {
if(p[i][j] != -1)res++;//1-8但是周围没有零,需要点一次
}
}
printf("Case #%d: %d\n",cases,res);
}
return 0;
}