AcWing 190. ×Ö´®±ä»» (BFS×îÄÑ°æ±¾ Ë«Ïò¹ãËÑ£©

#include<bits/stdc++.h>
using namespace std;
const int N=110;
string A,B;
int cnt;
string a[N],b[N];
int extend(queue<string>&q,unordered_map<string,int>&da,unordered_map<string,int>&db,string a[],string b[]){
    for(int k=0,qk=q.size();k<qk;k++){
        string t=q.front();
        q.pop();
        for(int i=0;i<t.size();i++){
            for(int j=0;j<cnt;j++){
                if(t.substr(i,a[j].size())==a[j]){
                    string st=t.substr(0,i)+b[j]+t.substr(i+a[j].size());
                    if(da.count(st))continue;
                    if(db.count(st))return da[t]+1+db[st];
                    da[st]=da[t]+1;
                    q.push(st);
                }
            }
        }
    }
    return 11;
}
int bfs(){
    queue<string>qa,qb;
    unordered_map<string,int>da,db;
    qa.push(A),qb.push(B);
    da[A]=0,db[B]=0;
    while(qa.size()&&qb.size()){
        int t;
        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;
    }
    return -1;
    
}
int main(){
    cin>>A>>B;
    while(cin>>a[cnt]>>b[cnt])cnt++;
    int res=bfs();
    if(res==-1)puts("NO ANSWER!");
    else cout<<res<<endl;
}