双向BFS

190.字串变换

概述：如何用最少的次数根据现有规则，将字符串A变为字符串B
题目连接：https://www.acwing.com/problem/content/description/192/
一个朴素的思想就是，把A字符串的所有能转变规则的地方都转变一次，就相当于从A字符串拓展出几条不同的通路来到达一个新的节点，然后依次类推，最后与B字符串连接，这样的问题其实还是一个最短路的问题，可以用DFS也可以BFS，以BFS为例，假设每次决策数量是 K，那么如果直接BFS，最坏情况下的搜索空间是$O(K^{10})$，如果我们用双向BFS，复杂度可以降到$O(2K^{5})$
思路：从初始字符串和结果字符串同时进行bfs，一层的一层的进行，通过判断bfs树的大小来决定下一次bfs拓展哪个方向，用一个map来记录各种枚举的字符串需要几次转换，然后直到两端相遇

题外话：扩展要一层一层的扩展，只扩展一层中的一部分可能结果不对

c++

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
#include <queue>
using namespace std;
int n;
vector<string> a;
vector<string> b;
string A, B;
int extend(queue<string>& q, unordered_map<string, int>&da, unordered_map<string, int>& db, 
    vector<string> &a, vector<string> &b)
{
    int d = da[q.front()];
    while (q.size() && da[q.front()] == d)
    {
        auto t = q.front();
        q.pop();
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < t.size(); j ++ )
                if (t.substr(j, a[i].size()) == a[i])
                {
                    string r = t.substr(0, j) + b[i] + t.substr(j + a[i].size());
                    //string r = t.replace(j, a[i].size(), b[i]);
                    if (db.count(r)) return da[t] + db[r] + 1;
                    if (da.count(r)) continue;
                    da[r] = da[t] + 1;
                    q.push(r);
                }
    }

    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.empty() && !qb.empty()) {
        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 -1;
}
int main() {
    string s1, s2;
    cin >> A >> B;
    while (cin >> s1 >> s2) {
        n++;
        a.push_back(s1);
        b.push_back(s2);
    }
    int t = bfs();
    if (t == -1) puts("NO ANSWER!");
    else cout << t << endl;
    return 0;
    
}