本题目需要同时记录男孩女孩两人的状态,所以双向bfs找最短路(两人轮流bfs),对于鬼直接考虑曼哈顿距离即可(因为鬼无视墙的限制)
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
const int N=810;
int n,m;
int T;
char g[N][N];
int st[N][N];
P ghost[2],boy,girl;
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
bool check(int x,int y,int k){
if(x<0||x>=n||y<0||y>=m||g[x][y]=='X') return false;
for(int i=0;i<2;i++){
if(abs(x-ghost[i].first)+abs(y-ghost[i].second)<=2*k) return false; //小于两个鬼曼哈顿距离的两倍
}
return true;
}
int bfs(){
queue<P> qb,qg;
qb.push(boy);
qg.push(girl);
int step=0;
while(!qb.empty()||!qg.empty()){
step++; //鬼先扩展
for(int i=0;i<3;i++){ //男孩走三步
for(int j=0,len=qb.size();j<len;j++){ //取出当前队列中的所有元素进行循环
P t=qb.front();
qb.pop();
int x=t.first,y=t.second;
if(!check(x,y,step)) continue;
for(int k=0;k<4;k++){ //4个方向
int a=x+dx[k],b=y+dy[k]; //注意是k
if(check(a,b,step)){
if(st[a][b]==2) return step; //2表示女孩走过,1表示男孩走过,0都没走过
if(!st[a][b]){
st[a][b]=1;
qb.push({a,b});
}
}
}
}
}
for(int i=0;i<1;i++){
for(int j=0,len=qg.size();j<len;j++){
P t=qg.front();
qg.pop();
int x=t.first,y=t.second;
if(!check(x,y,step)) continue;
for(int k=0;k<4;k++){
int a=x+dx[k],b=y+dy[k];
if(check(a,b,step)){
if(st[a][b]==1) return step;
if(!st[a][b]){
st[a][b]=2;
qg.push({a,b});
}
}
}
}
}
}
return -1;
}
int main(){
cin>>T;
while(T--){
cin>>n>>m;
memset(st,0,sizeof(st));
for(int i=0;i<n;i++) cin>>g[i];
int cnt=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(g[i][j]=='M') boy={i,j};
else if(g[i][j]=='G') girl={i,j};
else if(g[i][j]=='Z') ghost[cnt++]={i,j};
}
}
cout<<bfs()<<endl;
}
}
这个好欸
感谢
哇!码风我爱了!
代码不大缩进,其实一般的hhhh
感觉最清晰整洁的题解(%%%)
感谢您的认可