HDOJ 1195 Open the Lock (雙向BFS)

題意：要從一個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;   }