双向BFS(字串变换)

双向搜索——从初态和终态出发各搜索一半状态，产生两棵深度减半的搜索树，在中间交会、组合成最终的答案。

双向BFS——从起始状态、目标状态分别开始，两边轮流进行，每次各扩展一整层，当两边各自有一个状态在记录数组中发生重复时，就说明这两个搜索过程相遇了，可以合并得出起点到终点的最小步数

字串变换

双向BFS的时间复杂度分析：

假设字符串长度为L,替换规则一共N个，最坏情况下，使用N种规则，总共有LN种扩展方式，题目要求最多10步，则从起点和终点最多会扩展5步，所以搜索空间是2(LN) ^ 5

#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;

const int N = 6;

int n;

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.size(); i ++ )
        for(int j = 0; j < n; j ++ )
            if(t.substr(i, a[j].size()) == a[j])
            {
                string state = t.substr(0, i) + b[j] + t.substr(i + a[j].size());
                if(da.count(state)) continue;
                else if(db.count(state)) return da[t] + 1 + db[state];

                da[state] = da[t] + 1;
                q.push(state);
            }

     return 11;
}
int bfs(string A, string B)
{
    queue<string> qa, qb;
    unordered_map<string, int> da, db;
    qa.push(A), da[A] = 0;
    qb.push(B), db[B] = 0;

    while(qa.size() && qb.size())
    {
        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()
{
    string A, B;
    cin >> A >> B;

    while(cin >> a[n] >> b[n]) n ++;

    int step = bfs(A, B);

    if(step > 10) puts("NO ANSWER!");
    else cout << step << endl;
    return 0;
}