把估价函数去了, 改成bfs, 限制深度5
记着反向搜的时候, 修改的时候反着修改

#include <bits/stdc++.h>

using namespace std;

string a, b, ch[10][2];
int cnt, c, ans;
map<string, int> mp;
set<string> st;

int bfs(string s, bool f) {
    if (f && mp.count(s)) return mp[s];
    queue<pair<string, int>> q; q.push({ s, mp[s] = 0 });
    while (!q.empty()) {
        s = q.front().first; c = q.front().second; q.pop();
        for (int i = 1; i <= cnt; ++i)
            for (int p = s.find(ch[i][f], 0); p != string::npos; p = s.find(ch[i][f], p + 1)) {
                string cur = s;
                cur.replace(p, ch[i][f].size(), ch[i][f ^ 1]);
                if (!f) { if (!mp[cur]) { mp[cur] = mp[s] + 1; if (c < 4) q.push({ cur, c + 1 }); } }
                else if (mp[cur]) return mp[cur] + c + 1;
                else if (!st.count(cur)) st.insert(cur), q.push({ cur, c + 1 });
            }
    }
    return -1;
}

int main() {
    cin >> a >> b; mp[a] = 0;
    while (cin >> ch[++cnt][0] >> ch[cnt][1]);
    bfs(a, 0);
    ans = bfs(b, 1);
    if (~ans) cout << ans;
    else cout << "NO ANSWER!";
    return 0;
}