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  
          &

补充：软件开发 , C++ ,