记录编号	197002	评测结果	AAAAAAAA
题目名称	[NOIP 2002]字串变换	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	0.086 s
提交时间	2015-10-23 07:07:58	内存使用	0.31 MiB

#include <string>
#include <iostream>
#include <queue>
#include <cstdlib>
#include <map>
#include <fstream>
 
using namespace std;
 
string a, b, change[10][2], ans;
long cnt, len[10][2];
inline void bfs();
void fib(), fif();
map<string, long> mf, mb;
queue<string> qf, qb;
ifstream fin("string.in");
ofstream fout("string.out");
#define cin fin
#define cout fout

main() {
	string s, t;
	cin >> a >> b;
	cnt = 1;
	while (cin >> s >> t) {
		change[cnt][0] = s;
		change[cnt][1] = t;
		len[cnt][0] = s.length();
		len[cnt][1] = t.length();
		++cnt;
	}
	fin.close();
 
	--cnt;
	bfs();
}
 
inline void bfs() {
	qf.push(a);
	qb.push(b);
	mf[a] = 0;
	mb[b] = 0;
	while (! qf.empty() || ! qb.empty()) {
		if(!qf.empty()&&!qb.empty()&&mf[qf.front()]+mb[qb.front()]>10){
			cout << "NO ANSWER!";
			exit(0); 
		}
		if (! qf.empty() && ! qb.empty()) {
			if (mf[qf.front()] > mb[qb.front()])
				fib();
			else
				fif();
		}
		else if (! qf.empty() && qb.empty())
			fif();
		else
			fib();			
	}
	cout << "NO ANSWER!";
	fout.close();
	exit(0);
}

void fif() {
	if (! qf.empty()) {
		string f = qf.front();
		qf.pop();
		for (long i = 1; i <= cnt; ++i)
			for (long j = 0; j <= (long)f.length() - len[i][0]; ++j)
				if (f.substr(j, len[i][0]) == change[i][0]) {
					string c = f;
					c.replace(j, len[i][0], change[i][1]);
					if (mf.find(c) == mf.end()) {
						mf[c] = mf[f] + 1;
						if (mf[c] < 10)
							qf.push(c);
					}
					if (mb.find(c) != mb.end()) {
						if (mb[c] + mf[c] > 10)
							cout << "NO ANSWER!";
						else
							cout << mb[c] + mf[c];
						fout.close();
						exit(0);
					}
				}
	}
}

void fib() {
	if (! qb.empty()) {
		string b = qb.front();
		qb.pop();
		for (long i = 1; i <= cnt; ++i)
			for (long j = 0; j <= (long)b.length() - len[i][1]; ++j)
				if (b.substr(j, len[i][1]) == change[i][1]) {
					string c = b;
					c.replace(j, len[i][1], change[i][0]);
					if (mb.find(c) == mb.end()) {
						mb[c] = mb[b] + 1;
						if (mb[c] < 10)
							qb.push(c);
					}
					if (mf.find(c) != mf.end()) {
						if (mb[c] + mf[c] > 10)
							cout << "NO ANSWER!";
						else
							cout << mf[c] + mb[c];
						fout.close();
						exit(0);
					}
				}
		}
}