记录编号	434871	评测结果	AWAAAAAA
题目名称	[NOIP 2002]字串变换	最终得分	87
用户昵称	Hzoi_QTY	是否通过	未通过
代码语言	C++	运行时间	0.465 s
提交时间	2017-08-08 20:39:58	内存使用	0.08 MiB

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
string A,B,a[10],b[10];
int n=1,ans=11,cnt=0;
map<string,int> mp;
void dfs(string x,int len)
{//cout<<x<<" "<<len<<endl;
    cnt++;
    if(cnt>=40000){printf("NO ANSWER!\n");exit(0);}
	if(len>10)return;
	if(x.size()>20)return;
	if(len>ans)return;
	if(x==A)
	{
	    ans=min(ans,len);
	    return;
	}
	string f=x;int k;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<x.size();j++)
		{
		   k=x.find(b[i],j);
	       if(k<100&&k>=0)
	       {
		  	    int l=b[i].size();
		  	    x.replace(k,l,a[i]);
		  	    if(!mp.count(x))mp[x]=len,dfs(x,len+1);
		  	    else if(len<mp[x])dfs(x,len+1);
		  	    x=f;
		   }
		}
	}
}
int yjn()
{
	freopen("string.in","r",stdin);
	freopen("string.out","w",stdout);
	cin>>A>>B;
	while(cin>>a[n])
	{
		cin>>b[n];
		n++;
	}
	n--;
	mp[B]=++cnt;
	dfs(B,0);
	if(ans==11)printf("NO ANSWER!\n");
	else cout<<ans;
}
int qty=yjn();
int main(){;}