【更新】XMU 1308 单词联想 （双向BFS）
http://acm.xmu.edu.cn/JudgeOnline/problem.php?id=1308
题意：用给出的n(你<=10)种变换，将一个单词变成另一个单词。求最小步数，如果无法转换或转换次数大于8则输出Impossilbe。如果ABC → BCD表示型如XXABCXX的单词都可以一次变换成XXBCDXX。
思路：双向BFS搜索。搜索时用map查重，用string的replace对单词进行转换。具体过程详见代码注释部分。
另外，这道题转换规则存在一对多映射的情况……
【注意】双向BFS每次扩展结点后总是选择结点较少的一边进行下次搜索，而不是机械的两遍交替
后记：貌似之前对双向BFS的理解不太正确，刚才看刘汝佳的黑书时里面有这么一句话“每次扩展结点后总是选择结点较少的一边进行下次搜索，而不是机械的两遍交替”。因此对代码进行了修改，并调整了一个代码结构。时间和空间效率都大大提高了！~
新代码如下：
#include<iostream>#include<string>#include<queue>#include<map>using namespace std;struct node{ string word; int cnt;}now,tmp;map<string,int>vis;//正向标记已经访问过，关键字的值存到当前状态所走的步数map<string,int>back_vis;//反向标记已经访问过，关键字的值存到当前状态所走的步数queue<struct node>q;//正向BFS队列queue<struct node>back_q;//反向BFS队列string beg,end;//起始和终止的状态string change[11][2];//存储变换。int n;int back_bfs(int m)//当前搜索第m层{ while(!back_q.empty()&&m==back_q.front().cnt) { now=back_q.front(); back_q.pop(); for(int i=0;i<n;i++) { tmp=now; size_t pos; pos=tmp.word.find(change[i][1]);//查找是否有子串 if(pos!=tmp.word.npos) { tmp.word=tmp.word.replace(pos,change[i][1].size(),change[i][0]);//用string.replace直接对单词进行转换 if(vis.find(tmp.word)!=vis.end())//如果当前状态已经出现在正向BFS中，即找到了最优解 return tmp.cnt+vis[tmp.word]+1;//返回最优解步数 else if(back_vis.find(tmp.word)==back_vis.end())//否则判断这个状态在反向BFS中是否出现，没出现则将其标记并入队列 { tmp.cnt++; back_vis[tmp.word]=tmp.cnt; back_q.push(tmp); } } } } return -1;}int bfs(){ while(!q.empty())//清空队列 q.pop(); while(!back_q.empty())//清空队列 back_q.pop(); now.word=beg;//储存正向BFS的起始点信息，并标记入队列 now.cnt=0; vis[beg]=0; q.push(now); now.word=end;//储存反向BFS的起始点信息，并标记入队列 now.cnt=0; back_vis[end]=0; back_q.push(now); int m=0;//m记录当前搜索的层数 while(!q.empty()) { if(m!=q.front().cnt)//如果已经正向搜完一层则进行反向搜索这一层 { int ret=back_bfs(m); if(ret!=-1) return ret; else//如果反向没搜到，则将层数+1，继续正向搜索 { m++; continue; } } now=q.front(); q.pop(); for(int i=0;i<n;i++) { tmp=now; size_t pos; pos=tmp.word.find(change[i][0]);//查找是否有子串 if(pos!=tmp.word.npos) { tmp.word=tmp.word.replace(pos,change[i][0].size(),change[i][1]);//用string.replace直接对单词进行转换 if(back_vis.find(tmp.word)!=back_vis.end())//如果当前状态已经出现在反向BFS中，即找到了最优解 return back_vis[tmp.word]+tmp.cnt+1;//返回最优解步数 else if(vis.find(tmp.word)==vis.end())//否则判断这个状态在正向BFS中是否出现，没出现则将其标记并入队列 { tmp.cnt++; vis[tmp.word]=tmp.cnt; q.push(tmp); } } } } return -1;}int main(){ while(cin>>n) { vis.clear(); back_vis.clear(); cin>>beg>>end; string ip1,ip2; for(int i=0;i<n;i++) { cin>>ip1>>ip2;change[i][0]=ip1; change[i][1]=ip2; } if(beg==end) { cout<<"0"<<endl; continue; } int ret=bfs(); if(ret!=-1&&ret<=8) cout<<ret<<endl; else cout<<"Impossible"<<endl; } return 0;}