hdu 1195 Open the Lock

挺好的一道题目，双向bfs的题目，也能单向bfs写。不过双向写的代码太恶心了......还是因为不熟悉

题目大意：给出原密码和准确密码，对于原密码每次可以进行三个操作：
1：任意一位+1 且9+1=1
2：任意一位-1 且1-1=9
3：相邻两位互换，且首位和末位不是相邻的。
（密码只有四位数，每个数字1-9） 题目要求原密码变成准确密码的最少步数

单向bfs：

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <climits>//形如INT_MAX一类的
#define MAX 1050
#define INF 0x7FFFFFFF
# define eps 1e-5
//#pragma comment(linker, "/STACK:36777216") ///传说中的外挂
using namespace std;

struct node
{
    int num[4];
    int step;
}first,last;

bool vis[11][11][11][11];

bool ok(node t)
{
    int cnt = 0;
    for(int i=0; i<4; i++)
    {
        if(t.num[i] == last.num[i])
            cnt++;
    }
    if(cnt == 4)
        return 1;
    return 0;
}

void bfs()
{
    queue<node> q;

    vis[first.num[0]][first.num[1]][first.num[2]][first.num[3]] = 1;
    first.step = 0;
    q.push(first);
    while(!q.empty())
    {
        node tt = q.front();
        q.pop();
        node t;
        if(ok(tt))
        {
            cout << tt.step << endl;
            return ;
        }

        for(int i=0; i<4; i++)
        {
            t = tt;
            if(t.num[i] == 9)
                t.num[i] = 1;
            else
                t.num[i] ++;
            t.step = tt.step + 1;
            if(!vis[t.num[0]][t.num[1]][t.num[2]][t.num[3]])
            {
                q.push(t);

                vis[t.num[0]][t.num[1]][t.num[2]][t.num[3]] = 1;
            }
        }
        for(int i=0; i<4; i++)
        {
            t = tt;
            if(t.num[i] == 1)
                t.num[i] = 9;
            else
                t.num[i] --;
            t.step = tt.step + 1;
            if(!vis[t.num[0]][t.num[1]][t.num[2]][t.num[3]])
            {
                q.push(t);

                vis[t.num[0]][t.num[1]][t.num[2]][t.num[3]] = 1;
            }
        }
        for(int i=0; i<3; i++)
        {
            t = tt;
            swap(t.num[i],t.num[i+1]);
            t.step = tt.step + 1;
            if(!vis[t.num[0]][t.num[1]][t.num[2]][t.num[3]])
            {
                q.push(t);

                vis[t.num[0]][t.num[1]][t.num[2]][t.num[3]] = 1;
            }
        }
    }
}

int main()
{
    int t;
    char s[10],e[10];
    cin >> t;
    while(t--)
    {
        cin >> s >> e;
        for(int i=0; i<4; i++)
            first.num[i] = s[i] - '0';
        for(int i=0; i<4; i++)
            last.num[i] = e[i] - '0';
        memset(vis,0,sizeof(vis));
        bfs();
    }
    return 0;
}

双向bfs：

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <queue>//#pragma comment(linker, "/STACK:36777216") ///传说中的外挂
using namespace std;

struct node
{
    int num[4];
    int step;
} first,last;

int vis[11][11][11][11];
int vis2[11][11][11][11];

bool ok1(node a)
{
    if(vis[a.num[0]][a.num[1]][a.num[2]][a.num[3]] != -1)
        return 1;
    return 0;
}
bool ok2(node a)
{
    if(vis2[a.num[0]][a.num[1]][a.num[2]][a.num[3]] != -1)
        return 1;
    return 0;
}


void bfs()
{
    queue<node>q,q2;
    memset(vis,-1,sizeof(vis));
    memset(vis2,-1,sizeof(vis));

    int tmp1=0,tmp2=0;
    node t,tt;
    vis[first.num[0]][first.num[1]][first.num[2]][first.num[3]] = 0;
    first.step = 0;
    q.push(first);
    vis2[last.num[0]][last.num[1]][last.num[2]][last.num[3]] = 0;
    last.step = 0;
    q2.push(last);
    while(1)
    {
        while(!q.empty() && q.front().step == tmp1)
        {
            tt = q.front();
            q.pop();

            if(ok2(tt))
            {
                int k = vis2[tt.num[0]][tt.num[1]][tt.num[2]][tt.num[3]];
                cout << tt.step + k<< endl;
                return ;
            }

            for(int i=0; i<4; i++)
            {
                t = tt;
                if(t.num[i] == 9)
                    t.num[i] = 1;
                else
                    t.num[i] ++;
                t.step = tt.step + 1;
                if(ok2(t))
                {
                    int k = vis2[t.num[0]][t.num[1]][t.num[2]][t.num[3]];
                    cout << t.step + k<< endl;
                    return ;
                }
                if(!ok1(t))
                {
                    q.push(t);
                    vis[t.num[0]][t.num[1]][t.num[2]][t.num[3]] = t.step;
                }
            }
            for(int i=0; i<4; i++)
            {
                t = tt;
                if(t.num[i] == 1)
                    t.num[i] = 9;
                else
                    t.num[i] --;
                t.step = tt.step + 1;
                if(ok2(t))
                {
                    int k = vis2[t.num[0]][t.num[1]][t.num[2]][t.num[3]];
                    cout << t.step + k<< endl;
                    return ;
                }
                if(!ok1(t))
                {
                    q.push(t);
                    vis[t.num[0]][t.num[1]][t.num[2]][t.num[3]] = t.step;
                }
            }
            for(int i=0; i<3; i++)
            {
                t = tt;
                swap(t.num[i],t.num[i+1]);
                t.step = tt.step + 1;
                if(ok2(t))
                {
                    int k = vis2[t.num[0]][t.num[1]][t.num[2]][t.num[3]];
                    cout << t.step + k<< endl;
                    return ;
                }
                if(!ok1(t))
                {
                    q.push(t);
                    vis[t.num[0]][t.num[1]][t.num[2]][t.num[3]] = t.step;
                }
            }
        }
        tmp1 = q.front().step;
        //cout << "tmp1" <<' ' << tmp1 << endl;
        while(!q2.empty() && q2.front().step == tmp2)
        {
            tt = q2.front();
            q2.pop();
            if(ok1(tt))
            {
                int k = vis[tt.num[0]][tt.num[1]][tt.num[2]][tt.num[3]];
                cout << tt.step + k<< endl;
                return ;
            }

            for(int i=0; i<4; i++)
            {
                t = tt;
                if(t.num[i] == 9)
                    t.num[i] = 1;
                else
                    t.num[i] ++;
                t.step = tt.step + 1;
                if(ok1(t))
                {
                    int k = vis[t.num[0]][t.num[1]][t.num[2]][t.num[3]];
                    cout << t.step + k<< endl;
                    return ;
                }
                if(!ok2(t))
                {
                    q2.push(t);
                    vis2[t.num[0]][t.num[1]][t.num[2]][t.num[3]] = t.step;
                }
            }
            for(int i=0; i<4; i++)
            {
                t = tt;
                if(t.num[i] == 1)
                    t.num[i] = 9;
                else
                    t.num[i] --;
                t.step = tt.step + 1;
                if(ok1(t))
                {
                    int k = vis[t.num[0]][t.num[1]][t.num[2]][t.num[3]];
                    cout << t.step + k<< endl;
                    return ;
                }
                if(!ok2(t))
                {
                    q2.push(t);
                    vis2[t.num[0]][t.num[1]][t.num[2]][t.num[3]] = t.step;
                }
            }
            for(int i=0; i<3; i++)
            {
                t = tt;
                swap(t.num[i],t.num[i+1]);
                t.step = tt.step + 1;
                if(ok1(t))
                {
                    int k = vis[t.num[0]][t.num[1]][t.num[2]][t.num[3]];
                    cout << t.step + k<< endl;
                    return ;
                }
                if(!ok2(t))
                {
                    q2.push(t);
                    vis2[t.num[0]][t.num[1]][t.num[2]][t.num[3]] = t.step;
                }
            }
        }
        tmp2 = q2.front().step;
    }

}

int main()
{
    int t;
    char s[10],e[10];
    cin >> t;
    while(t--)
    {
        cin >> s >> e;
        for(int i=0; i<4; i++)
            first.num[i] = s[i] - '0';
        for(int i=0; i<4; i++)
            last.num[i] = e[i] - '0';
        bfs();
    }
    return 0;
}