双头BFS

本文主要是介绍双头BFS，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

牛客月赛100 D题，过了80%数据，调了一下午。。。烦死了。。。

还是没调试出来，别人的代码用5维的距离的更新有滞后性，要在遍历之前要去重。。。

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
char g[N][N];
int dis[N][N],d1[N][N];
int n,m,sx,sy;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int>PII;
queue<PII>q;
int bfs()
{while(q.size()){auto [x,y]=q.front();q.pop();for(int i=0;i<4;i++){int a=x+dx[i],b=y+dy[i];if(a<1||a>n||b<1||b>m)continue;if(dis[a][b]!=-1)continue;dis[a][b]=dis[x][y]+1;q.push({a,b});}}int ans=0x3f3f3f3f;memset(d1,-1,sizeof d1);queue<array<int,4>>p;p.push({sx,sy,sx,sy});d1[sx][sy]=0;while(p.size()){auto[x1,y1,x2,y2]=p.front();p.pop();for(int i=0;i<4;i++){int a=x1+dx[i],b=y1+dy[i];int c=x2-dx[i],d=y2-dy[i];if(a<1||a>n||b<1||b>m||c<1||c>n||d<1||d>m)continue;if(g[a][b]=='#'||g[c][d]=='#')continue;if(d1[a][b]!=-1)continue;d1[a][b]=d1[x1][y1]+1;if(g[a][b]=='@')ans=min(ans,d1[a][b]+dis[c][d]);p.push({a,b,c,d});}}if(ans!=0x3f3f3f3f)return ans;return -1;
}
int main()
{memset(dis,-1,sizeof dis);cin>>n>>m>>sx>>sy;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>g[i][j];if(g[i][j]=='@'){q.push({i,j});dis[i][j]=0;}}}cout<<bfs()<<endl;
//     for(int i=1;i<=n;i++){
//         for(int j=1;j<=m;j++){
//             cout<<dis[i][j];
//         }
//         puts("");
//     }   
//     puts("");
//     for(int i=1;i<=n;i++){
//         for(int j=1;j<=m;j++){
//             cout<<d1[i][j];
//         }
//         puts("");
//     }   return 0;
}

这篇关于双头BFS的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---