python/TangDou/AcWing/TwoWaySearch/190_bfs_BruteForce.cpp

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;

const int N = 10;
string a[N], b[N];          // 规则串，a[i]->b[i]
string A, B;                // 原始串
queue<pair<string, int>> q; // bfs专用队列
unordered_set<string> st;   // 是不是出现过

int n;

int bfs() {
    q.push({A, 0}); // 字符串，变换次数
    st.insert(A);   // A串出现过

    while (q.size()) {
        auto u = q.front();
        q.pop();

        string t = u.first;
        int d = u.second;
        if (t == B) return d; // 找到，返回路径长度

        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 ts = t.substr(0, i) + b[j] + t.substr(i + a[j].size());
                    if (st.count(ts) == 0) {
                        q.push({ts, d + 1});
                        st.insert(ts);
                    }
                }
            }
        }
    }
    return INF;
}

// 通过了 9/10个数据
// 最后一个测试点挂掉
// 简单暴搜：超时
int main() {
    cin >> A >> B;
    while (cin >> a[n] >> b[n]) n++;
    int ans = bfs();
    if (ans > 10)
        puts("NO ANSWER!");
    else
        printf("%d\n", ans);
    return 0;
}