记录编号	557029	评测结果	AEAEEAWE
题目名称	[NOIP 2002]字串变换	最终得分	37
用户昵称	锝镆氪锂铽	是否通过	未通过
代码语言	C++	运行时间	0.942 s
提交时间	2020-11-02 19:20:38	内存使用	4.91 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
using namespace std;

int cnt = 0;
string st, ed;
string c1[10], c2[10];

int step[100000];
string q[100000];
map <string, bool> vis;

void bfs();

int main() {
	freopen("string.in", "r", stdin);
	freopen("string.out", "w", stdout);
	cin >> st >> ed;
	while (cin >> c1[++cnt])
		cin >> c2[cnt];
	cnt--;
	bfs();
	return 0;
}

string change(string s, int i, int j) {
	string ans = "";
	if (i + c1[j].length() > s.length())
		return ans;
	for (int k = 0; k < c1[j].length(); k++)
		if (s[i + k] != c1[j][k])
			return ans;
	ans = s.substr(0, i);
	ans += c2[j];
	ans += s.substr(i + c1[j].length());
	return ans;
}

queue <string> que;
void bfs() {
	int cnt = 1, ccnt = 1, len, x, flag = 0;
	string now, nx;
	que.push(st);
	vis[st] = 1;
	while (!que.empty()) {
		x = cnt;
		cnt ++;
		now = que.front();
		que.pop();
		len = now.length();
		if (now == ed) {
			flag = 1;
			break;
		}
		for (int i = 0; i < len; i++)
			for (int j = 1; j <= cnt; j++) {
				nx = change(now, i, j);
				if (vis[nx])
					continue;
				que.push(nx);
				step[++ ccnt] = step[x] + 1;
				vis[nx] = 1;
			}
	}
	if (flag && step[x] <= 10)
		printf("%d\n", step[x]);
	else
		printf("NO ANSWER!\n");
}