传送门
https://www.luogu.com.cn/problem/P1032
找一个最短方案，考虑用bfs（没试过单向，但是系数很大）
更详细的解答
下面是代码理解（注释版）
// Problem:
// P1032 [NOIP2002 提高组] 字串变换
//
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1032
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
#include<string>
#include<unordered_map>//哈希表
#include<queue>
using namespace std;
string A,B;
string a[6],b[6];//方案
int len;int extend(queue<string>&q,unordered_map<string,int> &ha,unordered_map<string,int>
&hb,string a[],string b[]){int m=q.size();//每次只扩展一层while(m--){auto t=q.front();q.pop();for(int i=0;i<len;++i){//枚举方案for(unsigned int j=0;j<t.size();++j){//枚举起始位置if(t.substr(j,a[i].size())==a[i]){string ss=t.substr(0,j)+b[i]+t.substr(j+a[i].size());//字符串if(ha.count(ss)) continue;//如果这里之前有跳过if(hb.count(ss)) return ha[t]+hb[ss]+1;//对面之前有就返回答案ha[ss]=ha[t]+1;//更新q.push(ss); //入列}}}}return 11;
}int bfs(){unordered_map<string,int> ha,hb;queue<string> qa,qb;qa.push(A);qb.push(B);ha[A]=0,hb[B]=0;//别忘，不然count找不到int t=10;while(t--){int ans;if(qa.size()<qb.size()) ans=extend(qa,ha,hb,a,b);else ans=extend(qb,hb,ha,b,a);//反着传，因为两边对应关系不同if(ans<=10) return ans;}return 11;
}int main(){cin>>A>>B;while(cin>>a[len]){cin>>b[len++];//len记录个数}if(bfs()<=10) cout<<bfs()<<endl;else cout<<"NO ANSWER!";return 0;
}
