记录编号	167516	评测结果	AAAAAAAA
题目名称	[NOIP 2002]字串变换	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.569 s
提交时间	2015-06-25 23:31:31	内存使用	0.66 MiB

#include<cstdio>
#include<string>
#include<map>
#include<iostream>
#include<deque>
using namespace std;
const int SIZE=30000;
int tot=1,n=1,sw[SIZE],maxn=0x7fffffff;
int iq[SIZE]={0},ma=0;
string A,B;
string a[10],b[10];
string p[SIZE];
map<string,int> mp;
map<int,string> mp2;
deque<int> Q;
string C=("abcbaba");
void push(int x)
{
	if(iq[x]==0&&sw[x]<=10)
	{
		Q.push_back(x);
		iq[x]=1;
	}
}
void check(string s,int x)
{
	int q=a[x].length();
	int st=mp[s],fuck=0,tot2=0;
	string now[30];
	while(true)
	{
	int v=s.find(a[x],fuck);
	if(v==-1) break;
	tot2++;
	now[tot2]=s.substr(0,v);
	now[tot2]+=b[x];
	now[tot2]+=s.substr(v+q);
	if((A.length()<=B.length()&&now[tot2].length()>B.length()+ma)||now[tot2].length()>20) tot2--;
	fuck=v+q;
	//if(now[tot2]==C) cout<<tot2<<endl;
	//cout<<s<<" "<<a[x]<<" "<<now[tot2]<<" "<<v<<endl;
	}
	if(fuck==0) return;
	for(int j=1;j<=tot2;j++)
	{
	for(int i=0;i<=tot;i++)
	{
		if(now[j]==p[i])
		{
			if(sw[st]+1<sw[i]&&sw[st]<=10)
			{
				//cout<<now<<" "<<sw[i]<<endl;
				sw[i]=sw[st]+1;
				//cout<<now<<" "<<sw[i]<<endl;
				push(i);
			}
			goto NEXT;
		}
	}
	if(sw[st]+1<=10)
	{
	mp[now[j]]=++tot;
	sw[tot]=sw[st]+1;
	mp2[tot]=now[j];
	//cout<<now[j]<<" "<<" "<<sw[tot]<<endl;
	p[tot]=now[j];
	Q.push_back(tot);
	}
	NEXT:;
	}
}
int bfs()
{
	Q.push_back(1);
	for(int i=0;i<=SIZE;i++)
		sw[i]=maxn;
	iq[1]=1;
	sw[1]=0;
	while(!Q.empty())
	{
		int x=Q.front();iq[x]=0;Q.pop_front();
		string now=mp2[x];
		for(int i=1;i<=n;i++)
		{
			check(now,i);
			//cout<<now<<" "<<a[i]<<" "<<sw[x]<<endl;
			if(sw[0]!=maxn) return sw[0];
		}
	}
	return sw[0];
}
int main()
{
	freopen("string.in","r",stdin);
	freopen("string.out","w",stdout);
	cin>>A>>B;
	p[1]=A;
	p[0]=B;
	mp[A]=1;
	mp2[1]=A;
	mp[B]=0;
	mp2[0]=B;
	while(cin>>a[n]>>b[n])
	{
		int o=b[n].length()-2;
		ma=max(o,ma);
	    n++;
	}
	if(a[n][0]==a[n+1][0]) n--;
	//cout<<n<<endl;
	int ans=bfs();
	if(ans<=10) cout<<ans<<endl;
	else cout<<"NO ANSWER!"<<endl;
	//cout<<mp[C]<<endl;
	return 0;
}