对于搜索树分支很多且有明确起点和终点的情况时，可以采用双向搜索来减小搜索树的大小。
对于双向BFS来说，与单向最大的不同是双向BFS需要按层扩展，表示可能到达的区域。而单向BFS则是按照单个节点进行扩展，因为只有当前状态。
代码如下：
#include <bits/stdc++.h>using namespace std;const int maxn=810;char mp[maxn][maxn];int n,m,tot,step,f;struct node{ ???int x,y;}boy,girl,ghost[2];queue<node> q[2];//两个队列bool vis[2][maxn][maxn];//两个表示可达性void init(){ ???tot=0; ???while(q[0].size())q[0].pop(); ???while(q[1].size())q[1].pop(); ???memset(vis,0,sizeof(vis));}void read_and_parse(){ ???scanf("%d%d",&n,&m); ???for(int i=1;i<=n;i++){ ???????scanf("%s",mp[i]+1); ???????for(int j=1;j<=m;j++){ ???????????if(mp[i][j]==‘M‘)boy=(node){i,j}; ???????????if(mp[i][j]==‘G‘)girl=(node){i,j}; ???????????if(mp[i][j]==‘Z‘)ghost[tot++]=(node){i,j}; ???????} ???}}bool right(int x,int y){ ???if(x<1||x>n||y<1||y>m||mp[x][y]==‘X‘)return 0; ???if(abs(x-ghost[0].x)+abs(y-ghost[0].y)<=step<<1)return 0; ???if(abs(x-ghost[1].x)+abs(y-ghost[1].y)<=step<<1)return 0; ???return 1;}const int dx[]={0,0,1,-1};const int dy[]={1,-1,0,0};bool bfs(int idx){ ???int size=q[idx].size(); ???while(size--){ ???????node now=q[idx].front();q[idx].pop(); ???????if(!right(now.x,now.y))continue;//查看当前状态是否合法 ???????for(int i=0;i<4;i++){ ???????????int x=now.x+dx[i],y=now.y+dy[i]; ???????????if(!right(x,y)||vis[idx][x][y])continue; ???????????if(vis[1-idx][x][y])return 1; ???????????vis[idx][x][y]=1; ???????????q[idx].push((node){x,y}); ???????} ???} ???return 0;}void solve(){ ???step=0,f=0; ???q[0].push((node){boy.x,boy.y}); ???q[1].push((node){girl.x,girl.y}); ???while(q[0].size()||q[1].size()){ ???????++step; ???????for(int i=1;i<=3;i++)if(bfs(0)){f=1;break;}//每次扩展三层，表示走三步可能到达的状态 ???????if(bfs(1)){f=1;break;} ???} ???if(f)printf("%d\n",step); ???else puts("-1");}int main(){ ???int T;scanf("%d",&T); ???while(T--){ ???????init(); ???????read_and_parse(); ???????solve(); ???} ???return 0;}【HDU3085】nightmare2 双向BFS
原文地址：https://www.cnblogs.com/wzj-xhjbk/p/9800893.html