题意

• 给定两个字符串a，b，不超过6条变换规则，,如果能在十步以内使用变换规则将a变换为b，输出步数，否则输出NO ANSWER!

思路

• 对于最优极限情况，每一步内a可用6次变换规则，总复杂度为6^10
• 只要超过两种规则出现重复使用，单项搜索就会TLE
• 所以使用双向搜索，维护两个队列，一个从a用变换，一个从b用变换，维护两个映射，建立变换后的结果和步数的映射关系
• 对于bfs，最初需要判断如果a==b则无需进行后面的变换，直接返回0；
• 如果不返回零，就永远优先处理更小的那个队列
• 对于当前队列，取出队首串，对于每一个位置遍历每一个规则
• 如果匹配上了，产生一个新串tp
• 如果tp和另一个队列已产生的串中的某一个对上了，说明可以变换过去，直接返回步数，步数=a到tp+tp到b
• 如果tp没匹配上但在原队列中没有出现过，记录原队列到tp的步数并将tp加入队列
• 如果tp没匹配上且已经出现过了，忽略，直接continue；
• 最终判断返回的值能否小于十步，按要求输出即可

AC代码

#include<bits/stdc++.h>
using namespace std;
string A[6],B[6],a,b;
int n=0;
int deal(queue<string>&a,map<string,int>&ta,map<string,int>&tb,string A[],string B[]){
	string s=a.front();
	a.pop();
	for(int i=0;i<s.size();i++){
		for(int j=0;j<n;j++){
			if(s.substr(i,A[j].size())==A[j]){
				string tp=s.substr(0,i)+B[j]+s.substr(i+A[j].size());
				if(tb.count(tp))return ta[s]+1+tb[tp];
				else if(ta.count(tp)) continue;
				ta[tp]=ta[s]+1;a.push(tp);
			}
		}
	}
	return 11;
}
int bfs(string a,string b){
    if(a==b)return 0;
	queue<string>qa,qb;
	map<string,int>ta,tb;
	qa.push(a);
	qb.push(b);
	ta[a]=0;tb[b]=0;
	int s=11;
	while (qa.size()&&qb.size()){
		if(qa.size()<=qb.size()) s=deal(qa,ta,tb,A,B);
		else s=deal(qb,tb,ta,B,A);
		if(s<=10)return s;
	}
	return 11;
}
int main(){
	cin>>a>>b;
	while(cin>>A[n]>>B[n]) n++;
	int t=bfs(a,b);
	if(t>10)cout<<"NO ANSWER!"<<endl;
	else cout<<t<<endl;
	return 0;
}