题目来源：https://ac.nowcoder.com/acm/contest/88878/D
//
题意：迷宫中，两个人，走的每一步两个人的方向都是相反的，问两个人都走到地图中‘@’，最少的步数（地图上多个‘@’）。
//
思路：难点就在可以一个人到了，然后另一个人再独自走，就不用考虑到了那个人了。说明一个人独自走是可能会走重复路的，vis肯定就要开3维。结构体中f == 1代表都没到，f == 0有一个人到了，f状态改变后，vis[][][f]也刷新了，自然就可以走回头路了。
//
代码细节：
1：注意我存图是从下标0开始的，st_x,st_y要--“debug找半天”。
2：if(t == 1 || t == 2)，其中一个人到了，那么就把没到的人的坐标赋值给x1，y1，后续处理边界什么的只考虑x1,y1就行了。
//
题解：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+9;
int n,m,st_x,st_y;
char mp[N][N];
int vis[N][N][2];
int dx1[]={-1,1,0,0};
int dy1[]={0,0,-1,1};
int dx2[]={1,-1,0,0};
int dy2[]={0,0,1,-1};
struct Nod{
int x1,y1,x2,y2,f,step;
}temp,p;
queue<Nod>q;
void bfs(){
q.push({st_x,st_y,st_x,st_y,1,0});
while(!q.empty()){
temp=q.front();q.pop();
if(vis[temp.x1][temp.y1][temp.f]){ continue;}
vis[temp.x1][temp.y1][temp.f]=1;
if(temp.f){//两个都没到
for(int i=0;i<4;i++){
p.x1=temp.x1+dx1[i];
p.y1=temp.y1+dy1[i];
p.step=temp.step+1;
p.x2=temp.x2+dx2[i];
p.y2=temp.y2+dy2[i];
p.f=temp.f;
if(p.x1>=0&&p.x1<n&&p.x2>=0&&p.x2<n && p.y1>=0&&p.y1<m&&p.y2>=0&&p.y2<m && mp[p.x1][p.y1]!='#'&&mp[p.x2][p.y2]!='#'&&!vis[p.x1][p.y1][p.f]){
int t=0;
if(mp[p.x1][p.y1]=='@'){t+=1;}
if(mp[p.x2][p.y2]=='@'){t+=2;}
if(t==0){q.push(p);}//都没到
if(t==1){q.push({p.x2,p.y2,p.x1,p.y1,0,p.step});}//1到了
if(t==2){q.push({p.x1,p.y1,p.x2,p.y2,0,p.step});}//2到了
if(t==3){cout<<p.step<<endl;return;}//都到了
}
}
}
else{//其中一个到了
for(int i=0;i<4;i++){
p.x1=temp.x1+dx1[i];
p.y1=temp.y1+dy1[i];
p.step=temp.step+1;
p.f=temp.f;
if(p.x1>=0&&p.x1<n && p.y1>=0&&p.y1<m && mp[p.x1][p.y1]!='#'&&!vis[p.x1][p.y1][p.f]){
if(mp[p.x1][p.y1]=='@'){
cout<<p.step<<endl;return;
}
if(mp[p.x1][p.y1]=='.'){
q.push(p);
}
}
}
}
}
cout<<"-1"<<endl;
}
int main()
{
cin>>n>>m>>st_x>>st_y;
st_x-=1,st_y-=1;//mp是从0开始存的
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>mp[i][j];
}
}
bfs();
return 0;
}