第一个题解

#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
//#include<bits/stdc++.h>
using namespace std;
typedef unordered_map<string, int> USI; // 为了后面方便定义
typedef queue<string> QS;
const int N = 6;
string a[N], b[N];
string A, B;
int n;
int expand(QS& q, USI& da, USI& db, string a[N], string b[N]){
    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 st = t.substr(0, i) + b[j] + t.substr(i + a[j].size()); // 前面到从0开始，长度是i，加上规则中的，再加上后半部分
                if (da.count(st))   continue; // 如果做过，就跳过，算是一个剪枝优化吧
                if (db.count(st))   return da[t] + 1 + db[st]; // 值是从起点到当前的t点，加上到当前点的1，然后加上从终点走到当前点的距离
                da[st] = da[t] + 1; // 更新答案
                q.push(st);
            }
    return 11; // 如果无解就返回一个比10大的数就行
}
int bfs(){
    QS qa,qb; 
    USI 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 = expand(qa, da, db, a, b); 
        else    t=expand(qb, db, da, b, a); 
        if (t <= 10)    return t; 
    }
    return 11;
}
int main(){
    cin >> A >> B;
    while (cin >> a[n] >> b[n]) n++; 
    if (A == B){
        puts("0");
        return 0;
    }
    int step = bfs();
    if (step > 10)  puts("NO ANSWER!");
    else  printf("%d\n", step);
    return 0;
}