題意：要從一個4位數，變成另一個4位數。有3種變換方法：1、選擇一位加1（9+1變成1）；2、選擇一位減1（1-1變成9）；3、選擇相鄰的兩位交換其數值（第一位與第四位不相鄰）。求最少的步數。 思路：這是我第一次寫出雙向BFS~用兩個隊列分別記錄正向的bfs和反向的back_bfs，用map進行查重，map中的第二個值記錄當前關鍵字的步數。搜一層正向的，並判斷有沒有在反向中出現；再搜一層反向的，並判斷有沒有在正向中出現。循環上面的搜索過程，直到搜到正向和反向中有交集（即搜到相同關鍵字）位置，將正向和反向的步數加和即可。 注意：一定要一層一層搜！！！！ 第一次寫雙向BFS，代碼可能寫得不好，僅供參考 [cpp] #include<iostream> #include<algorithm> #include<string> #include<queue> #include<map> using namespace std; struct node { string password; int cnt; }now,tmp; string beg,end; map<string,int>back_vis; map<string,int>vis; queue<struct node>q; queue<struct node>back_q; int back_bfs(int n)//反向BFS，每次只搜一層,即第n層 { while(back_q.front().cnt<=n) { now=back_q.front(); back_q.pop(); for(int i=0;i<4;i++) { //各個位-1 tmp=now; if(tmp.password[i]!='1') tmp.password[i]--; else tmp.password[i]='9'; if(vis.find(tmp.password)!=vis.end())//判斷是否在正向隊列中找到 return tmp.cnt+1+vis[tmp.password]; if(back_vis.find(tmp.password)==back_vis.end()) { tmp.cnt++; back_q.push(tmp); back_vis[tmp.password]=tmp.cnt; } //各個位+1 tmp=now; if(tmp.password[i]!='9') tmp.password[i]++; else tmp.password[i]='1'; if(vis.find(tmp.password)!=vis.end())//判斷是否在正向隊列中找到 return tmp.cnt+1+vis[tmp.password]; if(back_vis.find(tmp.password)==back_vis.end()) { tmp.cnt++; back_q.push(tmp); back_vis[tmp.password]=tmp.cnt; } } for(int i=0;i<3;i++) { tmp=now; swap(tmp.password[i],tmp.password[i+1]); if(vis.find(tmp.password)!=vis.end())//判斷是否在正向隊列中找到 return tmp.cnt+1+vis[tmp.password]; if(back_vis.find(tmp.password)==back_vis.end()) { tmp.cnt++; back_q.push(tmp); back_vis[tmp.password]=tmp.cnt; } } } return -1; } int bfs() { while(!q.empty()) q.pop();//清空正向BFS的隊列 now.password=beg; now.cnt=0; q.push(now); vis[beg]=0; while(!q.empty()) { int n=q.front().cnt; while(q.front().cnt<=n) { now=q.front(); q.pop(); for(int i=0;i<4;i++) { //各個位-1 tmp=now; if(tmp.password[i]!='1') tmp.password[i]--; else tmp.password[i]='9'; if(back_vis.find(tmp.password)!=back_vis.end())//判斷是否在反向隊列中找到 return tmp.cnt+1+back_vis[tmp.password]; if(vis.find(tmp.password)==vis.end()) { tmp.cnt++; q.push(tmp); vis[tmp.password]=tmp.cnt; } //各個位+1 tmp=now; if(tmp.password[i]!='9') tmp.password[i]++; else tmp.password[i]='1'; if(back_vis.find(tmp.password)!=back_vis.end())//判斷是否在反向隊列中找到 return tmp.cnt+1+back_vis[tmp.password]; if(vis.find(tmp.password)==vis.end()) { tmp.cnt++; q.push(tmp); vis[tmp.password]=tmp.cnt; } } for(int i=0;i<3;i++) { tmp=now; swap(tmp.password[i],tmp.password[i+1]); if(back_vis.find(tmp.password)!=back_vis.end())//判斷是否在反向隊列中找到 return tmp.cnt+1+back_vis[tmp.password]; if(vis.find(tmp.password)==vis.end()) { tmp.cnt++; q.push(tmp); vis[tmp.password]=tmp.cnt; } } } int ret=back_bfs(now.cnt); if(ret!=-1) return ret; } } int main() { int t; while(cin>>t) { while(t--) { cin>>beg; cin>>end; vis.clear();//清空map back_vis.clear();//清空map while(!back_q.empty()) back_q.pop();//清空反向BFS的隊列 now.password=end; now.cnt=0; back_q.push(now); back_vis[end]=0;//將反向BFS的起始點入隊列標記 int ret=bfs(); cout<<ret<<endl; } } return 0; }
