双向bfs模板

原题链接
是个裸的双向BFS的题，看到一份比较好的代码，我以前好像都是写的两个BFS的，而他这个写在一起了，而且更好得体现了一层一层的搜索的思想
比如原来做题的时候就遇到过，因为我是 输出调试法来debug的，所以原来打印坐标的时候不知道这个点是在第几步搜出来的，其实搜完一层后，新加的就是下一层了
这个就作为一个模板了

写的时候还写错了，第二个找到目标后马上就退出，所以BFS里面的return要写在循环外面

#include"bits/stdc++.h"
#define out(x) cout<<#x<<"="<<x
#define C(n,m) (m>n?0:(long long)fac[(n)]*invf[(m)]%MOD*invf[(n)-(m)]%MOD)
using namespace std;
typedef long long LL;
const int maxn=1e3+5;
const int MOD=1e9+7;
char G[maxn][maxn];
bool vis[2][maxn][maxn];
int N,M;
struct Node
{
int x,y;
Node() {}
Node(int x,int y):x(x),y(y) {}
};
Node ST1,ST2;//表示两个起点
int dx[8]= {1,0,-1,0,1,1,-1,-1};
int dy[8]= {0,1,0,-1,1,-1,1,-1};
queue<Node>que[2];
int BFS(int cmd)
{
int sz=que[cmd].size();//精髓~队列里有的就是上一次各个方向搜索的
while(sz--)
{
Node u=que[cmd].front();
que[cmd].pop();
for(int i=0; i<4+(cmd==0?4:0); i++) //第一个是8个方向
{
int xx=u.x+dx[i];
int yy=u.y+dy[i];
if(xx<1||xx>N||yy<1||yy>M||G[xx][yy]=='#'||vis[cmd][xx][yy])continue;
if(vis[cmd^1][xx][yy])return 1;//要在这里一找到就退出,不能像普通的写在循环外面
vis[cmd][xx][yy]=1;
que[cmd].push(Node(xx,yy));
}
}
return 0;
}
int solve()
{
while(!que[0].empty())que[0].pop();
while(!que[1].empty())que[1].pop();
que[0].push(ST1);
que[1].push(ST2);
memset(vis,0,sizeof vis);
vis[0][ST1.x][ST1.y]=1;
vis[1][ST2.x][ST2.y]=1;
int step=0;
while(que[0].size()||que[1].size())//只要有一个还能走就继续走
{
step++;
if(BFS(0))return step;
if(BFS(1))return step;
if(BFS(1))return step;//第二个人要走两步,所以这里弄两次
}
return -1;
}
int main()
{
while(cin>>N>>M)
{
for(int i=1; i<=N; i++)
{
for(int j=1; j<=M; j++)
{
cin>>G[i][j];
if(G[i][j]=='C')ST1=Node(i,j);
else if(G[i][j]=='D')ST2=Node(i,j);
}
}
int ans=solve();
if(ans==-1)puts("NO");
else
{
puts("YES");
cout<<ans<<endl;
}
}
}
/*
4 5
. C # # .
# . . # .
# # . D .
# . # . .
*/

最后

以上就是丰富小馒头为你收集整理的双向bfs模板的全部内容，希望文章能够帮你解决双向bfs模板所遇到的程序开发问题。

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