Acwing.687 扫雷
687. 扫雷 - AcWing题库
题号:Acwing.687 扫雷
题目类型:深搜 or 宽搜
简要做题思路:输入 -> 循环遍历数组,统计每个数字八个方位雷的个数 -> 深搜查看若是0则单击一次可以解决多少 -> 如果不是0则需一个一个按 -> 输出
#include <bits/stdc++.h>
using namespace std;
const int N = 310;
int l[N][N], m, n;
char str[N][N];
bool st[N][N];
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1}, dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
void dfs(int x, int y) {
st[x][y] = 1; //用st数组标记已访问
for (int i = 0; i < 8; i++) {
int nx = x + dx[i], ny = y + dy[i];//用偏移量分别遍历八个方向的数据
if (nx < 0 || nx >= m || ny < 0 || ny >= m) continue;
if (str[nx][ny] == '*' || st[nx][ny]) continue; //越界/是雷/已访问过 均需跳出循环
st[nx][ny] = 1;//标记该点可以被清除
if (l[nx][ny] == 0) dfs(nx, ny); //如果当前位置仍然是0,继续深搜
}
}
int scan(int x, int y) {
int cnt = 0;//记录八个方向雷的个数
for (int i = 0; i < 8; ++ i) {
int a = x + dx[i], b = y + dy[i];//用偏移量分别遍历八个方向的数据
if (a < 0 || a >= m || b < 0 || b >= m) continue;//越界情况->跳出
if (str[a][b] == '*') cnt++;//当前位置是雷->记录
}
return cnt;
}
int main() {
cin >> n;
for (int c = 1; c <= n;c++) {
cin >> m;
memset(st, 0, sizeof st);//初始化十分重要
memset(l,0,sizeof l);
for (int i = 0; i < m;i++) cin >> str[i];//整行读入
for (int i = 0; i < m;i++){
for (int j = 0; j < m;j++){
if (str[i][j] == '*') l[i][j] = -1; //用-1在l数组中标记出雷
else l[i][j] = scan(i, j);//扫描周围有多少个雷,填入l数组中
}
}
int res = 0;//开始统计共需多少步
//首先专门特判出现0的情况
for (int i = 0; i < m; i++){
for (int j = 0; j < m; j++){
if (!st[i][j] && l[i][j] == 0) {//判断是0且非雷
dfs(i, j);//将为0的情况用深搜全部解决
res++;//只需要点击一次完成
}
}
}
for (int i = 0; i < m; ++ i)
for (int j = 0; j < m; ++ j)
if (!st[i][j] && str[i][j] == '.')
res++;//除了0以外剩下的所有非雷的地方每个需要点击一次
printf("Case #%d: %d\n", c, res);
}
return 0;
}