P1032 80points，求查

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

int cnt = 1; string A, B;
string a[10], b[10];
struct node{
	string s; int step;
}; queue<node> q;
map<string, bool> mp;

void bfs(){
	q = queue<node>(); q.push({A, 0}); mp[A] = true;
	while (!q.empty()){
		string u = q.front().s;
		int step = q.front().step; q.pop();
		//cout << u << " " << step << endl;
		
		if (step > 10) {cout << "NO ANSWER!" << endl; exit(0);}
		if (u == B) {cout << step << endl; exit(0);}
		
		for (int i = 1; i <= cnt; i++){
			int pos = u.find(a[i]);
			if (pos == -1)	continue;
			string tmp = u.substr(0, pos) + b[i];
			tmp += u.substr(pos + a[i].length());
			if (!mp.count(tmp)){
				mp[tmp] = true;
				q.push({tmp, step + 1});
			}
		}
	}
}

int main(){
	cin >> A >> B;
	while (cin >> a[cnt] >> b[cnt])
		cnt++;
	cnt--;
	
	bfs();
	
	cout << "NO ANSWER!" << endl;
	
	return 0;
}

评测详情