洛谷P1032 [NOIP2002 提高组] 字串变换

ac代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 15;
struct node{
	string str;
	int step;
};
string a, b;
string orginal[N];
string translated[N];
int n, ans;
 
map<string,int> ma;
 
string trans(const string &str, int i, int j){
	//初始化新串为空格 
	string ans = " ";

//	if(i + orginal[j].length() > str.length()){
//		return ans;
//	}
    
	//进行匹配 看j串是否为str的子串 
	for(int k = 0; k < orginal[j].length(); ++k){
		//如果不是返回空串 
		if(str[i + k] != orginal[j][k]){
			return ans;
		}
	}
	//进行修改操作 
	ans = str.substr(0, i);
	ans += translated[j];
	ans += str.substr(i + orginal[j].length());
	//返回修改过的新串 
	return ans;
}

void bfs(){
	queue<node>q;
	node s;
	s.str = a;
	s.step = 0;
	q.push(s);
	
	while(!q.empty()){
		node u = q.front();
		q.pop();
		string temp;
		//记录当前串是否被搜索过 
		if(ma.count(u.str) == 1){
			continue;
		}
		//如果当前串和目标串匹配 
		if(u.str == b){
			//更新答案最优步数为当前步数 
			ans = u.step;
			break;
		}
		//将当前串存入map中 
		ma[u.str] = 1;
		//遍历当前串每一位 
		for(int i = 0; i < u.str.length(); ++i){
			//遍历所有变换规则 
			for(int j = 0; j < n; ++j){
				//新串 
				temp = trans(u.str, i, j);
				//如果有新串 
				if(temp != " "){
					//将其存入队列中 
					node v;
					//新串 
					v.str = temp;
					//步数 
					v.step = u.step + 1;
					//放入队列 
					q.push(v);
				}
			}
		}
	}
	//进行最小步数判断 
	if(ans > 10 || ans == 0){
		cout<<"NO ANSWER!"<<endl;
	}else{
		cout << ans << endl;
	}
}


int main(){
	cin >> a >> b;
	while(cin >> orginal[n] >> translated[n]){
		n++;
	}
	bfs();
	return 0;
}