题解

#include<bits/stdc++.h>
using namespace std;
string s1,s2,a,b;
string st[10],ed[10];
int cnt;
map<string,int> mp1,mp2;
bool flag;
queue<string> q1,q2;
int bfs(map<string,int> &mp1,map<string,int> &mp2,queue<string> &q,string a[],string b[]){
	int len=q.size();
	for(int k=1;k<=len;k++){
		string p=q.front();
		q.pop();
//		printf("第%d步得到的字符串为%s\n",step,p.c_str());
		for(int i=0;i<p.length();i++){
			for(int j=1;j<=cnt;j++){
				if(p.substr(i,a[j].length())==a[j]){
					string now=p.substr(0,i)+b[j]+p.substr(i+a[j].length());
					if(mp1.count(now)) continue;
					if(mp2.count(now)) return mp1[p]+1+mp2[now];
					mp1[now]=mp1[p]+1;
					q.push(now);
				}
			}
		}
	}
	return 11;
}
int main(){
	cin>>s1>>s2;
	while(cin>>a>>b){
		st[++cnt]=a;
		ed[cnt]=b;
	}
	mp1[s1]=0,mp2[s2]=0;
	q1.push(s1),q2.push(s2);
	while(!q1.empty() && !q2.empty()){
		int ans=0;
		if(q1.size()<=q2.size()) ans=bfs(mp1,mp2,q1,st,ed);
		else ans=bfs(mp2,mp1,q2,ed,st);
		if(ans<=10){
			cout<<ans;
			return 0;
		}
	}
	cout<<"NO ANSWER!";
	return 0;
}