记录编号	595682	评测结果	AAAAAAAA
题目名称	[NOIP 2002]字串变换	最终得分	100
用户昵称	郑霁桓	是否通过	通过
代码语言	C++	运行时间	0.069 s
提交时间	2024-10-15 20:41:43	内存使用	3.46 MiB

#include<bits/stdc++.h>
using namespace std;
long long n,p,as,tp;
string a,b,x[15],y[15],pp,sp;
map<string,long long>mp1,mp2;
long long bfs(){
    queue<string>q1,q2;
    while(!q1.empty()){
        q1.pop();
    }
    while(!q2.empty()){
        q2.pop();
    }
    q1.push(a);
    q2.push(b);
    mp1[a]=mp2[b]=p=0;
    while(++p<=5){
        while(mp1[q1.front()]==p-1){
            pp=q1.front();
            q1.pop();
            for(int i=1;i<=n;i++){
                as=0;
                while(as<pp.length()){
                    if((long long)pp.find(x[i],as)==-1){
                        break;
                    }
                    sp=pp;
                    tp=sp.find(x[i],as);
                    sp.erase(tp,x[i].length());
                    sp.insert(tp,y[i]);
                    if(mp1.find(sp)!=mp1.end()){
                        as++;
                        continue;
                    }
                    if(mp2.find(sp)!=mp2.end()){
                        return p*2-1;
                    }
                    q1.push(sp);
                    mp1[sp]=p;
                    as++;
                }
            }
        }
        while(mp2[q2.front()]==p-1){
            pp=q2.front();
            q2.pop();
            for(int i=1;i<=n;i++){
                as=0;
                while(as<pp.length()){
                    if((long long)pp.find(y[i],as)==-1){
                        break;
                    }
                    sp=pp;
                    tp=sp.find(y[i],as);
                    sp.erase(tp,y[i].length());
                    sp.insert(tp,x[i]);
                    if(mp2.find(sp)!=mp2.end()){
                        as++;
                        continue;
                    }
                    if(mp1.find(sp)!=mp1.end()){
                        return p*2;
                    }
                    q2.push(sp);
                    mp2[sp]=p;
                    as++;
                }
            }
        }
    }
    return 0;
}
int main(){
    freopen("string.in","r",stdin);
    freopen("string.out","w",stdout);
    cin>>a>>b;
    while(cin>>x[++n]){
        cin>>y[n];
    }
    n--;
    p=bfs();
    if(p){
        cout<<p;
    }else{
        cout<<"NOANSWER!";
    }
    return 0;
}