题目传送门

P1032 [NOIP 2002 提高组] 字串变换（疑似错题） - 洛谷

思路

这道题直接BFS暴力搜索即可，但是完全暴力可能会超时（题目数据比较水，所以是可能），所以使用了双向广搜可以降一些时间复杂度。在搜索的时候用unordered_map记录下在不同情况下的字符串的层数，当出现u在另一个unordered_map也出现时就直接返回两者之和ma[u] + mb[u] 。

双向广搜模板


int bfs() {
    queue<string> qa, qb;
    qa.push(A);
    qa.push(B);
    while (!qa.empty() && !qb.empty()) {
        string u, v;
        if (qa.size() < qb.size()) {
            extend(qa,.....);
        }
        else {
            extend(qb,.....);
        }
    }
}

AC代码：

#include<bits/stdc++.h>
using namespace std;
unordered_map<string, int> ma;
unordered_map<string, int> mb;
string a, b;
queue<string> qa, qb;
set<pair<string, string>> st;


int bfs() {
    qa.push(a), qb.push(b);
    while (!qa.empty() && !qb.empty()) {
        string u, v;
        if (qa.size() < qb.size()) {
            u = qa.front();
            qa.pop();
            if (mb[u] > 0 || u == b) return ma[u] + mb[u];
            int idx = -1;
            for (auto [x, y] : st) {
                idx = u.find(x, idx + 1);
                while (idx != -1) {
                    v = u.substr(0, idx);
                    v += y;
                    idx += (int)x.size();
                    if (idx < (int)u.size()) v += u.substr(idx);
                    idx = u.find(x, idx);
                    if (ma[v] > 0) continue;
                    ma[v] = ma[u] + 1;
                    qa.push(v);
                }
            }
        }
        else {
            u = qb.front();
            qb.pop();
            if (ma[u] > 0 || u == a) return ma[u] + mb[u];
            int idx = -1;
            for (auto [x, y] : st) {
                idx = u.find(y, idx + 1);
                while (idx != -1) {
                    v = u.substr(0, idx);
                    v += x;
                    idx += (int)y.size();
                    if (idx < (int)u.size()) v += u.substr(idx);
                    idx = u.find(y, idx);
                    if (mb[v] > 0) continue;
                    mb[v] = mb[u] + 1;
                    qb.push(v);
                }
            }
        }
    }
    return -1;
}

void solve() {
    cin >> a >> b;
    string x, y;
    while (cin >> x >> y) {
        st.insert({ x,y });
    }
    int t = bfs();
    if (t == -1) {
        cout << "NO ANSWER!" << endl;
    }
    else {
        cout << t << endl;
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
    //cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}