记录编号	67188	评测结果	AAAAAAAA
题目名称	[NOIP 2002]字串变换	最终得分	100
用户昵称	艮山谦	是否通过	通过
代码语言	C++	运行时间	0.429 s
提交时间	2013-08-09 17:08:07	内存使用	3.21 MiB

#include<iostream>
#include<fstream>
#include<string>
#include<queue>
using namespace std;
string start,target,A[12],B[12];
bool f[65536]={0};
int N,l[6];
unsigned BKDRHash(string str)
{
	unsigned hash=0,seed=131,i;
    for(i=0;str[i];i++)
		hash=hash*seed+str[i];
	return (hash&0xffff);
}
void Input(void)
{
	freopen("string.in","r",stdin);
	freopen("string.out","w",stdout);
	cin>>start>>target;
	int i=0;
	while(!cin.eof())
	{	
		cin>>A[i];
		l[i]=A[i].length();
		if(l[i]==0)continue;
		cin>>B[i];
		i++;
	}
    N=i;
}
void BFS(void)
{
	unsigned i,pos,h,nowd;
	string s;
	queue<string>q;
	queue<int>d;
    q.push(start);
    d.push(0);
    while(!q.empty()&&d.front()<10)
	{
		s=q.front();
		nowd=d.front();
		for(i=0;i<N;i++)
		{
			pos=s.find(A[i],0);
			while(pos!=string::npos)
			{
				s.replace(pos,l[i],B[i]);
				h=BKDRHash(s);
				if(f[h]==false)
				{
					q.push(s);
					d.push(nowd+1);
					if(s==target){cout<<d.back()<<endl;goto end;}
					f[h]=true;
			    }
			    s=q.front();
                pos=s.find(A[i],pos+1);				
			}
		}
		q.pop();
		d.pop();
	}
    cout<<"NO ANSWER!"<<endl;
	end:
	return;
}
int main()
{
    Input();
	BFS();
	return 0;
}