一道难得的搜索好题，题目大意很简单，这里不再赘述，主要说一下思路
当然普通的bfs答案是正确的，但是在CH上评测会TLE一个点，所以我们采用效率更高的双向bfs
从初始状态和目标状态分别搜索，建立两个队列，分别扩展状态。如果一个队列扩展的状态已经被另一个队列搜索过了，那么便出现答案了。
另外，使用map可以对字符串进行标记，replace可以自动替换字符串，详见代码。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 #include <map> 6 #include <algorithm> 7 #include <string> 8 using namespace std; 9 string a,b,aa[10],bb[10]; 10 int n=1; 11 queue<string> q1; 12 queue<string> q2; 13 map<string,int> vis; 14 map<string,int> dis; 15 string now,noww,neww; 16 int main() { 17 cin>>a>>b; 18 while(cin>>aa[n]>>bb[n]) n++; 19 n--; 20 q1.push(a); 21 q2.push(b); 22 vis[a]=1; 23 vis[b]=2; 24 dis[a]=0; dis[b]=0; 25 if(a==b) { 26 puts("0"); 27 return 0; 28 } 29 while((!q1.empty())&&(!q2.empty())) { 30 if(q1.size()<=q2.size()) { 31 now=q1.front(); 32 q1.pop(); 33 int d=dis[now]; 34 for(int i=1;i<=n;i++) { 35 noww=now; 36 while(1) { 37 int m=noww.find(aa[i]); 38 if(m==-1) break ; 39 neww=now; 40 neww.replace(m,aa[i].size(),bb[i]); 41 if(vis[neww]!=1) { 42 if(vis[neww]==2) { 43 if(dis[neww]+d+1<=10) printf("%d\n",dis[neww]+d+1); 44 else puts("NO ANSWER!"); 45 return 0; 46 } 47 vis[neww]=1; 48 dis[neww]=d+1; 49 q1.push(neww); 50 } 51 noww[m]=‘!‘; 52 } 53 } 54 } 55 else { 56 now=q2.front(); 57 q2.pop(); 58 int d=dis[now]; 59 for(int i=1;i<=n;i++) { 60 noww=now; 61 while(1) { 62 int m=noww.find(bb[i]); 63 if(m==-1) break ; 64 neww=now; 65 neww.replace(m,bb[i].size(),aa[i]); 66 if(vis[neww]!=2) { 67 if(vis[neww]==1) { 68 if(dis[neww]+d+1<=10) printf("%d\n",dis[neww]+d+1); 69 else puts("NO ANSWER!"); 70 return 0; 71 } 72 vis[neww]=2; 73 dis[neww]=d+1; 74 q2.push(neww); 75 } 76 noww[m]=‘!‘; 77 } 78 } 79 } 80 } 81 puts("NO ANSWER!"); 82 return 0; 83 }
原文：https://www.cnblogs.com/shl-blog/p/10587042.html
