分析

• 使用两个队列从起点和终点同时扩展，每次选择状态比较少的一端进行扩展，这样可以大大降低需要搜索的空间。

• 注意：每次必须将一层的点全部扩展，否则会出现问题

上图来自：题解

#include <iostream>
#include <queue>
#include <unordered_map>

using namespace std;

const int N = 6;

int n;  // 规则的数目
string a[N], b[N];  // 变换规则，从a变为b

// q: 需要扩展的队列; da: 扩展的新状态距离存储的位置
// db: 检查新状态另一侧是否已经扩展到了
int extend(queue<string> &q, unordered_map<string, int> &da, 
           unordered_map<string, int> &db, string a[], string b[]) {
    for (int k = 0, sk = q.size(); k < sk; k++) {
        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;
                    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;  // 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);
        // 如果t>10，存在两种情况: (1) 还没扩展完毕; (2) 实际步数确实大于10
        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;
}