记录编号	154287	评测结果	AAAAAAAA
题目名称	[NOIP 2002]字串变换	最终得分	100
用户昵称	devil	是否通过	通过
代码语言	C++	运行时间	0.027 s
提交时间	2015-03-22 09:33:37	内存使用	0.48 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <map>
#include <queue>
#include <cstring>
#include <sstream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN=30010;
const int MAX_INT=0x7fffffff;
const int MAXT=210;

struct node
{
    string s;
    int steps;
    node() {s.clear();steps=0;}
    void print()
    {
        cout<<s;
        printf("    %d\n",steps);
    }
};

string A,B;
string a[MAXN],b[MAXN];
int n=0,ans=11;

map<string,int> words1;
map<string,int> words2;

void BFS()
{
    queue<node> q1;

    queue<node> q2;

    node st1;st1.s=A;
    q1.push(st1);
    words1[st1.s]=1;

    node st2;st2.s=B;
    q2.push(st2);
    words2[st2.s]=1;

    while(!q1.empty()&&!q2.empty())
    {
        if(!q1.empty())
        {
            node t1=q1.front();
            q1.pop();///t1.print();
            if(t1.steps>ans) {continue;}
            if(words2[t1.s]!=0)
            {
                int t=words2[t1.s];
                if(t1.s==B) t--;
                ans=min(ans,t1.steps+t);

            }
            for(int i=0;i<n;i++)
            {
                int d=t1.s.find(a[i].c_str());
                while(d!=-1)
                {
                    node nt1=t1;
                    nt1.steps++;
                    int len=a[i].length();
                    nt1.s.replace(d,len,b[i].c_str());
                    if(!words1[nt1.s])
                    {
                        words1[nt1.s]=nt1.steps;
                        q1.push(nt1);
                    }
                    words1[nt1.s]=min(words1[nt1.s],nt1.steps);
                    d=t1.s.find(a[i].c_str(),d+len);
                }
            }
        }

        if(!q2.empty())
        {
            node t2=q2.front();
            q2.pop();///t2.print();
            if(t2.steps>ans) {continue;}
            if(words1[t2.s]!=0)
            {
                int t=words1[t2.s];
                if(t2.s==A) t--;
                ans=min(ans,t2.steps+t);
            }
            for(int i=0;i<n;i++)
            {
                int d=t2.s.find(b[i].c_str());
                while(d!=-1)
                {
                    node nt2=t2;
                    nt2.steps++;
                    int len=b[i].length();
                    nt2.s.replace(d,len,a[i].c_str());
                    if(!words2[nt2.s])
                    {
                        words2[nt2.s]=nt2.steps;
                        q2.push(nt2);
                    }
                    words2[nt2.s]=min(words2[nt2.s],nt2.steps);
                    d=t2.s.find(b[i].c_str(),d+len);
                }
            }
        }
    }
    ///printf("NO ANSWER!\n");
}
int main()
{
    ///freopen("sample_data.in","r",stdin);
    ///freopen("data.in","r",stdin);
    ///freopen("data.out","w",stdout);
    freopen("string.in","r",stdin);
    freopen("string.out","w",stdout);
    cin>>A>>B;scanf("\n");
    while(cin>>a[n]>>b[n])
    {
        scanf("\n");n++;
    }
    words1.clear();
    words2.clear();
    BFS();
    if(ans==11) printf("NO ANSWER!\n");
    else printf("%d\n",ans);
    ///printf("%d\n",MAX_INT+1);
    return 0;
}