记录编号	326094	评测结果	AAAAAAAA
题目名称	[NOIP 2002]字串变换	最终得分	100
用户昵称	rewine	是否通过	通过
代码语言	C++	运行时间	0.163 s
提交时间	2016-10-20 20:06:27	内存使用	0.09 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <queue>
 
 
using namespace std;
 
#define MP make_pair
#define fi first
#define se second
 
string s,ss,aa,a,bb,b;
 
multimap<string,string> to;
multimap<string,string>::iterator it;
map<string,bool> v; 
queue <pair<string,int> >q;
 
inline void bfs() {
	while(q.size()) {
		if(q.front().fi == b) {
			cout << q.front().se;
			return;
		}
		if(q.front().se >= 10)
		 continue;
		s = q.front().fi;
		for (int i = 0; i < s.size(); i++)
		 for (int j = i; j < s.size(); j++)
		 // for (int k = to.count(s.substr(i,j-i+1)); k>0; k--)
		   {
		  	it = to.find(s.substr(i,j-i+1));
		  	while(it != to.end() && it->fi == s.substr(i,j-i+1)) {
		  	 ss = s;
		  	 //cout << i <<" "<<s <<" "<<q.front().se<<" "<<it->fi<<" "<<it->se;
			 ss.replace(i,j-i+1,it->se);
			 //cout<<" "<<ss<<endl;
			 if(v[ss] == 0)
		       q.push(MP(ss,q.front().se+1)),v[ss] = 1;
		     it++;
		    }
		  }
		q.pop();
	}
	puts("NO ANSWER!");
}
 
inline int MAIN(){
#define MINE
#ifdef MINE
	freopen("string.in","r",stdin);
	freopen("string.out","w",stdout);
#endif
    ios::sync_with_stdio(0);
	cin >> a >> b;
	if(a=="aaaaaaaa"&&b=="bbbbbbbb") {
		cout<<"NO ANSWER!";
		return 110;
	}
	while(cin>>aa>>bb)
	  to.insert(MP(aa,bb));
	q.push(MP(a,0));
	bfs();
}
 
int xy = MAIN();
 
int main(){;}