双向BFS模板

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int dmax=1010,d[5][2]={{0,0},{1,0},{0,1},{-1,0},{0,-1}};
int a[dmax][dmax],p[dmax][dmax],ans[dmax][dmax];
struct node{
int x,y,s;
node(){
x=y=s=0;
}
};
struct node q[dmax*dmax];
struct node qu[dmax*dmax];
int main(){
int i,j,k,m,n,sx,sy,ex,ey;
scanf("%d%d",&n,&m);
scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
scanf("%d",&a[i][j]);
int f=0,l=1,s=0,t=1,tx,ty;
q[1].x=sx;
q[1].y=sy;
q[1].s=0;
qu[1].x=ex;
qu[1].y=ey;
qu[1].s=0;
p[sx][sy]=1;
p[ex][ey]=2;
while (f<l || s<t){
f++;
for (i=1;i<=4;i++){
tx=q[f].x+d[i][0];
ty=q[f].y+d[i][1];
if (tx<0 || ty<0 || tx>n || ty>m || a[tx][ty]==1) continue;
if (p[tx][ty]==2){
printf("%dn",ans[tx][ty]+q[f].s+1);
return 0;
}
if (p[tx][ty]==1) continue;
q[++l].x=tx;
q[l].y=ty;
q[l].s=q[f].s+1;
ans[tx][ty]=q[l].s;
p[tx][ty]=1;
}
s++;
for (i=1;i<=4;i++){
tx=qu[f].x+d[i][0];
ty=qu[f].y+d[i][1];
if (tx<0 || ty<0 || tx>n || ty>m || a[tx][ty]==1) continue;
if (p[tx][ty]==1){
printf("%dn",ans[tx][ty]+qu[f].s+1);
return 0;
}
if (p[tx][ty]==2) continue;
qu[++t].x=tx;
qu[t].y=ty;
qu[t].s=qu[s].s+1;
ans[tx][ty]=qu[t].s;
p[tx][ty]=2;
}
}
return 0;
}

最后

以上就是害怕毛豆为你收集整理的双向BFS模板的全部内容，希望文章能够帮你解决双向BFS模板所遇到的程序开发问题。

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