题解 | #[NOIP2002]字串变换#

#include <iostream>
#include <map>
#include <queue>

using namespace std;

int n = 1;
string s, t;
string a[10], b[10];

map <string, int> A, B;
queue <string> qup, qbl;

int bfs() {
    int step = 0;

    qup.push(s), A[s] = 0;
    qbl.push(t), B[t] = 0;

    while(++ step <= 5) {
        while(A[qup.front()] == step - 1) {
            string t = qup.front();

            for(int i = 1; i <= n; i++) {
                int pos = 0;        //开始寻找a[i]的位置

                while(pos < t.size()) {
                    if(t.find(a[i], pos) == t.npos) break;

                    string tem = t;
                    tem.replace(tem.find(a[i], pos), a[i].size(), b[i]);

                    if(A.find(tem) != A.end()) {pos ++; continue;}
                    if(B.find(tem) != B.end()) return step * 2 - 1;

                    qup.push(tem), A[tem] = step, pos ++;
                }
            }

            qup.pop();
        }

        while(B[qbl.front()] == step - 1) {
            string t = qbl.front();

            for(int i = 1; i <= n; i++) {
                int pos = 0;

                while(pos < t.size()) {
                    if(t.find(b[i], pos) == t.npos) break;

                    string tem = t;
                    tem.replace(tem.find(b[i], pos), b[i].size(), a[i]);

                    if(B.find(tem) != B.end()) {pos ++; continue;}
                    if(A.find(tem) != A.end()) return step * 2;

                    qbl.push(tem), B[tem] = step, pos ++;
                }
            }

            qbl.pop();
        }
    }

    return -1;
}

int main() {
    cin >> s >> t;

    while(cin >> a[n] >> b[n]) n++;

    int ans = bfs();

    if(ans == -1) cout << "NO ANSWER!";
    else cout << ans;

    return 0;
}