双向bfs——噩梦（模板）

传送门：AcWing 177. 噩梦 - AcWing

思路：一眼丁真，鉴定为“春春的bfs”，使用两个队列分别存男孩和女孩的行动路径，注意与鬼之间的曼哈顿距离不要小于当前时间常数time乘2。男孩的行动距离最多是3，所以在扩展时要扩展3次。

代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int>PII;
typedef long long ll;
const int N=1e3+10;
char d[N][N];
int st[N][N];
int n,m;
PII ghost[2],boy,girl;
bool check(int x,int y,int k)
{
if(x<0||x>=n||y<0||y>=m||d[x][y]=='X') return false;
for(int i=0;i<2;i++)
if(abs(x-ghost[i].first)+abs(y-ghost[i].second)<=k*2) return false;
return true;
}
int bfs()
{
int cnt=0;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
memset(st,0,sizeof st);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
if(d[i][j]=='M') boy={i,j};
else if(d[i][j]=='G') girl={i,j};
else if(d[i][j]=='Z') ghost[cnt++]={i,j};
}
int time=0;
queue<PII>qb,qg;
qg.push(girl);
qb.push(boy);
while(qb.size()||qg.size())
{
time++;
for(int i=0;i<3;i++)
{
for(int j=0,len=qb.size();j<len;j++)
{
auto t=qb.front();
qb.pop();
int x=t.first;
int y=t.second;
if(!check(x,y,time))continue;
for(int k=0;k<4;k++)
{
int a=x+dx[k],b=y+dy[k];
if(check(a,b,time))
{
if(st[a][b]==2) return time;
if(!st[a][b])
{
st[a][b]=1;
qb.push({a,b});
}
}
}
}
}
for(int j=0,len=qg.size();j<len;j++)
{
auto t=qg.front();
qg.pop();
int x=t.first;
int y=t.second;
if(!check(x,y,time))continue;
for(int k=0;k<4;k++)
{
int a=x+dx[k],b=y+dy[k];
if(check(a,b,time))
{
if(st[a][b]==1) return time;
if(!st[a][b])
{
st[a][b]=2;
qg.push({a,b});
}
}
}
}
}
return -1;
}
int
main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
scanf("%s",d[i]);
printf("%dn",bfs());
}
return 0;
}

最后

以上就是个性冥王星为你收集整理的双向bfs——噩梦（模板）的全部内容，希望文章能够帮你解决双向bfs——噩梦（模板）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。