牛客小白月赛24C 十面埋伏（bfs+模拟）

题目链接


思路：说实话一开始没怎么读懂题意，但乱搞也就过了。。。先把士兵当成墙，bfs求一下可以遍历到的点，接着再看看这些点的上下左右是否有士兵，有的话就变成*。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 505 ;
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
char s[maxn][maxn];
int n,m,vis[maxn][maxn];
void bfs()
{
	queue<pair<int,int>>q;
	q.push({0,0});
	vis[0][0]=true;
	while(!q.empty())
	{
		pair<int,int>t=q.front();
		q.pop();
		for(int j=0;j<4;++j)
		{
			int nx=t.first+dir[j][0],ny=t.second+dir[j][1];
			if(nx<0||nx>=n||ny<0||ny>=m||vis[nx][ny]||s[nx][ny]=='#') continue;
			q.push({nx,ny});
			vis[nx][ny]=true;
		}
	}
}
int  main()
{
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;++i) scanf("%s",s[i]);
	bfs();
	for(int i=0;i<n;++i)
	for(int j=0;j<m;++j)
	{
		if(s[i][j]=='#') continue;
		for(int k=0;k<4;++k)
		{
			int nx=i+dir[k][0],ny=j+dir[k][1];
			if(nx<0||nx>=n||ny<0||ny>=m) continue;
			if(s[nx][ny]=='#'&&vis[i][j]) s[i][j]='*';
		}
	}
	for(int i=0;i<n;++i) printf("%s\n",s[i]);
}