字串变换

参考题解

思路

由于字符串变换的状态很多，空间复杂度和时间复杂度过大，所以采用双向广搜

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unordered_map<string, int> usi;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, -1, 1};
const double eps = 1e-6;
const int N = 1e5 + 10;
int n, m;
string a[6], b[6], A, B;

// bfs所用队列qa; 从A开始的距离da; 从B开始的距离db; 字符串变换规则a和b
int extend(queue<string> &qa, usi &da, usi &db, string a[], string b[])
{
    int d = da[qa.front()];
    while (qa.size() && da[qa.front()] == d) // while循环，确保每次extend扩展一层
    {
        string t = qa.front();
        qa.pop();

        for (int i = 0; i < t.size(); i++) // 从字符串t的位置i开始匹配
        {
            for (int j = 0; j < n; j++) // 匹配n种规则
            {
                if (t.substr(i, a[j].size()) == a[j])
                {
                    string nxt = t.substr(0, i) + b[j] + t.substr(i + a[j].size());
                    if (db.count(nxt))
                        return da[t] + 1 + db[nxt];
                    if (da.count(nxt))
                        continue;
                    da[nxt] = da[t] + 1;
                    qa.push(nxt);
                }
            }
        }
    }
    return 11;
}
int bfs()
{
    if (A == B) // 注意特判0步的情况
        return 0;
        
    queue<string> qa, qb;
    usi da, db;
    qa.push(A), qb.push(B);
    da[A] = db[B] = 0;
    int t, step = 0;
    while (qa.size() && qb.size())
    {
        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;
        if (++step == 10)
            return 11;
    }
    return 11;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> A >> B;
    while (cin >> a[n] >> b[n])
        n++;

    int t = bfs();
    if (t <= 10)
        cout << t << '\n';
    else
        cout << "NO ANSWER!";
    return 0;
}