线上OJ:
一本通:http://ybt.ssoier.cn:8088/problem_show.php?pid=1970 (opens in a new tab)
AcWing:https://www.acwing.com/problem/content/464/ (opens in a new tab)
洛谷:https://www.luogu.com.cn/problem/P2670 (opens in a new tab)
核心思想:
这是一道基础的 dfs模板题,只需要对每个点判断四周的8个点是否有雷即可,不需要在dfs中继续dfs。
step1. 如果是*,则直接输出*
step2. 如果不是*,则dfs周边8个点后,直接输出结果
#include <bits/stdc++.h>
#define MAXN 105
using namespace std;
int n, m;
char a[MAXN][MAXN];
int dx[8]={-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8]={-1, 0, 1, -1, 1, -1, 0, 1};
void dfs(int x, int y)
{
int cnt = 0;
for(int i = 0; i < 8; i++)
{
int x1 = x + dx[i];
int y1 = y + dy[i];
if( x1 >= 1 && x1 <= n && y1 >= 1 && y1 <= m && a[x1][y1] == '*')
cnt++;
}
cout << cnt;
return;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j++)
cin >> a[i][j];
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= m; j++)
if(a[i][j]=='*') cout << '*'; // 如果是*,则直接输出
else dfs(i, j); // 如果不是*,则dfs周边8个点
cout << endl;
}
return 0;
}