引入

双向BFS指的是，从起点和终点同时往中间搜；

这种搜法是对普通BFS的一个优化；

下面是单向BFS和双向BFS的直观感受；

应用场景

一般应用于需要将整体抽象成一个状态的搜索；

因为这样的搜索状态很多，直接单向搜的话，可能会TLE、MLE；

比如魔板、字串变换；

而像武士风度的牛（求最短路）、城堡问题（求连通块及其大小）的优化效果不明显；

实现方式

方式一、

起点扩展一层、终点扩展一层，以此类推；

方式二、

相对于方式一是一个优化；

从当前状态较少的一边开始搜，避免极端情况(即一边状态很多，一边状态很少)；

例题

字串变换

优化程序的简单计算

如果单向搜索的话，假设有6个规则，变换10次；

那么时间为$6^{10}$；

如果我们双向搜索，只需要搜$2\ast 6^5$;

可以看出是极大的优化了；

---

思路

这里采用从状态总数较少的一边进行扩展，具体见代码注释；

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <string>using namespace std;typedef long long ll;const int N = 1e5 + 10;string start,over;string ra[10],rb[10];//规则 ra(i) -> rb(i)int n;typedef unordered_map<string,int> umsi;int extend(queue<string> &que,umsi& da,umsi& db,string ra[],string rb[]){string u = que.front();que.pop();//枚举起点for(int i=0;i<u.size();++i){//枚举规则for(int j=0;j<n;++j){//如果匹配的上if(u.substr(i,ra[j].size()) == ra[j]){//按规则变换string now = u.substr(0,i) + rb[j] + u.substr(i+ra[j].size());//如果另一个队列存在now 直接返回if(db.count(now)) return db[now] + da[u] + 1;//不重复入队if(da.count(now)) continue;da[now] = da[u] + 1;que.push(now);}}}//没有接触到对方return -1;
}int bfs(){if(start == over) return 0;queue<string> qa,qb;//从起点搜的队列、从终点搜的队列umsi disa,disb;//距离disa[start] = disb[over] = 0;qa.push(start);qb.push(over);//必须两边队列都有值才能继续扩展int res;while(!qa.empty() && !qb.empty()){//从起点扩展if(qa.size() <= qb.size()){res = extend(qa,disa,disb,ra,rb);}//从终点扩展else{res = extend(qb,disb,disa,rb,ra);}if(res!= -1 && res <= 10) return res;}return -1;
}void solve(){cin >> start >> over;//[0,n)while(cin >> ra[n] >> rb[n]) ++n;int ans = bfs();if(ans == -1) cout << "NO ANSWER!\n";else cout << ans << '\n';
}int main(){std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);solve();return 0;
}