记录编号	148041	评测结果	AAAAAAAA
题目名称	[NOIP 2002]字串变换	最终得分	100
用户昵称	albertxwz	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2015-02-06 13:56:02	内存使用	0.31 MiB

#include<cstdio>
#include<iostream>
#include<map>
#include<string>
#include<queue>
#define LOCAL
using namespace std;

typedef struct{
	string s;
	int num;
}point;

map<string,int> m1,m2;
queue<point> q1,q2;
string change[6][2];
point s1,s2;
int k=0,ans;

string become(string now,int pos,int n,string tmp){
	return now.replace(pos,n,tmp);
}

bool dbfs(){
	while(!q1.empty()&&!q2.empty()){
		s1=q1.front();
		int len=s1.s.length();
		for(int i=0;i<len;i++)
			for(int j=0;j<k;j++){
				int tmp=change[j][0].length();
				if(i+tmp-1<len&&!s1.s.compare(i,tmp,change[j][0])&&!m1.count(become(s1.s,i,tmp,change[j][1]))){
					s2.s=become(s1.s,i,tmp,change[j][1]);
					s2.num=q1.front().num+1;
					if(s2.num>10)return false;
					m1[s2.s]=s2.num;
					q1.push(s2);
					if(m2.count(s2.s)){
						ans=s2.num+m2[s2.s];
						return true;
					}
				}
			}
		q1.pop();
		s1=q2.front();
		len=s1.s.length();
		for(int i=0;i<len;i++)
			for(int j=0;j<k;j++){
				int tmp=change[j][1].length();
				if(i+tmp-1<len&&!s1.s.compare(i,tmp,change[j][1])&&!m2.count(become(s1.s,i,tmp,change[j][0]))){
					s2.s=become(s1.s,i,tmp,change[j][0]);
					s2.num=q2.front().num+1;
					if(s2.num>10)return false;
					m2[s2.s]=s2.num;
					q2.push(s2);
					if(m1.count(s2.s)){
						ans=s2.num+m1[s2.s];
						return true;
					}
				}
			}
		q2.pop();
	}
	return false;
}

int main(){
#ifdef LOCAL
	freopen("string.in","r",stdin);
	freopen("string.out","w",stdout);
#endif
	cin>>s1.s>>s2.s;
	if(s1.s==s2.s){
		cout<<0<<endl;
		return 0;
	}
	s1.num=s2.num=0;
	q1.push(s1);
	q2.push(s2);
	m1[s1.s]=0;
	m2[s2.s]=0;
	while(cin>>change[k][0]>>change[k][1])k++;
	if(dbfs())cout<<ans<<endl;
	else printf("NO ANSWER!");
	return 0;
}