记录编号	435069	评测结果	AAAAAAAA
题目名称	[NOIP 2002]字串变换	最终得分	100
用户昵称	하루Kiev	是否通过	通过
代码语言	C++	运行时间	0.830 s
提交时间	2017-08-09 07:38:47	内存使用	17.48 MiB

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <queue>
#include <map>
using namespace std;
string s;
string s1,s2;
string sa[20],sb[20];
int zz,n,la[20],lb[20],ans;
//map<string,int> mp;
typedef pair<string,int> wx;
//queue<wx> q;
string q1[2000005];
int q2[2000005],head,tail;
bool pd,vis[2000005];
unsigned long long p=131,Hash;

int hash_(string s){
	Hash=0;
	for(int i=0;i<s.size();i++)
	   Hash=Hash*p+s[i];
	return Hash%1000007;
}
int main(){
	freopen("string.in","r",stdin);
    freopen("string.out","w",stdout);
	cin>>s1>>s2;
	while(cin>>sa[++zz]){
		 la[zz]=sa[zz].size();
	     cin>>sb[zz];
	     lb[zz]=sb[zz].size();
		 n++;
	}
	/*for(int i=1;i<=n;i++)cout<<sa[i]<<" ";
	cout<<endl;
	for(int i=1;i<=n;i++)cout<<la[i]<<" ";
	cout<<endl;*/
	//q.push(wx(s1,0));
	head=1;
	q1[++tail]=s1;
	q2[tail]=0;
	while(head<=tail){
	      string ss=q1[head];
	      int step=q2[head];
	      //cout<<ss<<" "<<endl;
	      if(step>=10) break;
	      for(int i=1;i<=n;i++){
	      	  //cout<<step<<" ";
	      	  int change=ss.find(sa[i],0);
	      	  while(true){
	      	  	    if(change==-1) break;
	      	  	    //cout<<ss<<" -> "; 
	      	  	    ss.replace(change,la[i],sb[i]);
	      	  	    //cout<<ss<<endl;
	      	  	    int bj=hash_(ss);
	      	  	    if(vis[bj]==0){
	      	  	       //q.push(wx(ss,step+1));
	      	  	       q1[++tail]=ss;
	      	  	       q2[tail]=step+1;
	      	  	       if(ss==s2&&pd==0) {cout<<step+1;return 0;}
					   vis[bj]=1;
					}//cout<<ss<<"!!";
					ss=q1[head];
					//cout<<ss<<"!!!";
					change=ss.find(sa[i],change+1);
			 }
		  }
		  head++;
	}
	if(!pd) cout<<"NO ANSWER!";
	//else printf("%d",ans);
}
/*
a aaaaa
a a112233445566778899
778899 a
112233 a
445 a
566 a
55 a

5
*/