题目描述
解题思路
解题思路参考https://www.acwing.com/solution/content/5434/ 详细注释参考https://www.acwing.com/solution/content/41647/ 双向BFS定义参考视频
双向BFS的优点: 1.双向bfs能够极大地提高速率 2.单向bfs如果是次扩展，那么双向bfs就是 双向BFS的缺点: 1.必须确定问题的起始状态和结束状态，如果两个状态有一个不确定则无法使用。 2.在对状态进行标记时往往涉及状态的压缩
双向bfs一般用来求解初始状态和结束状态的已知的最优解问题
问：双向BFS搜索的结束条件是什么？如何处理
搜索的边界就是两个BFS遇到了相同的状态(位置),返回最少步骤
问：双向BFS搜索的结束条件是什么？如何处理
搜索的边界就是两个BFS遇到了相同的状态(位置),返回最少步骤
问：为什么在bfs的时候 终止条件是2个队列都不为空呢 为什么不是只要有一个队列不为空就继续搜下去呢
有一个为空说明从那个状态开始已经搜完所有状态却没有和第一个队列交集，说明无解，只有两个都不为空才继续搜
问：为什么要优先搜长度小的那个队列
哪个方向的队列的长度更小一些，搜索空间就更小一些，速度更快，从该方向开始扩展
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 6;
int n;
string A, B;
string a[N], b[N];
/* 扩展函数
参数：扩展的队列，到起点的距离，到终点的距离，规则，规则
返回值：满足条件的最小步数*/
int extend(queue<string>& q, unordered_map<string, int>& da, unordered_map<string, int>& db, string a[], string b[])
{
string t = q.front();
q.pop();
for (int i = 0; i < t.length(); i++) // t从哪里开始扩展
for (int j = 0; j < n; j++) // 枚举规则
if (t.substr(i, a[j].size()) == a[j]) //如果t这个字符串的一段= 规则，比如= xyz，才可以替换
{
string state = t.substr(0, i) + a[j] + t.substr(i + a[j].size()); // 变换之后的结果state:前面不变的部分+ 变化的部分 + 后面不变的部分
if (db.count(state)) return da[t] + 1 + db[state]; // state状态是否落到b里面去，两个方向会师，返回最小步数
if (da.count(state)) continue; // 如果该状态之前已扩展过，
da[state] = da[t] + 1;
q.push(state);
}
return 11;
}
int bfs()
{
if (A == B) return 0;
queue<string>qa, qb;
unordered_map<string,int>da, db;
qa.push(A), qb.push(B);
da[A] = 0, db[B] = 0;
while (qa.size() && qb.size()) // qa和qb都有值，说明可以扩展过来，否则说明是不相交的
{
int t;
// 哪个方向的队列的长度更小一些，空间更小一些，从该方向开始扩展
if (qa.size() <= qb.size()) t = extend(qa,da,db,a,b);
else t = extend(qb,db,da,b,a);
if (t <= 10) return t;
}
return 11;
}
int main()
{
cin >> A >> B;
while (cin >> a[n] >> b[n]) n++;
int step = bfs();
if (step > 10) puts("NO ANSWER!");
else cout << step << endl;
return 0;
}
