学步园

       一道容易又复杂的搜索题。题意：有两个骰子A和B，骰子有六个面，上面的数字分别是1到6。有4种操作，分别是把骰子的上下变成前后，上下变成后前，上下变成左右和上下变成右左。现在按上下左右前后的顺序输入两个骰子每个面的数字，问骰子A能否通过以上操作变换成骰子B，能的话输出最小操作数，否则输出-1。

       我的解题思路：其实就是个裸BFS，来个6维数组来存储状态是否走过，然后每次搜索判断是否到达目标状态，裸的没话说了。

       我的解题代码：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

struct dice     //定义骰子的结构体
{
    int num[6];     //骰子每个面的数字，分别是上下左右前后
    int step;       //表示到达当前状态需要从初始状态变换的步数
    void read() //输入当前骰子每个面的信息
    {
        for (int i=0; i<6; ++i) scanf("%d", &num[i]);
    }
};

dice a, b;
queue <dice> q;
bool vis[7][7][7][7][7][7]; //判断当前状态是否走过

void Bfs();

bool Mycmp(dice x, dice y); //判断是否到达目标状态

int main()
{
    while (~scanf("%d %d %d %d %d %d", &a.num[0], &a.num[1], &a.num[2], &a.num[3], &a.num[4], &a.num[5]))
    {
        b.read();
        Bfs();
    }
    return 0;
}

void Bfs()
{
    dice x, y;
    a.step = 0;
    while (!q.empty()) q.pop();     //就是因为忘了清空队列，WA了5次，哭瞎
    memset(vis, false, sizeof(vis));
    q.push(a);
    vis[a.num[0]][a.num[1]][a.num[2]][a.num[3]][a.num[4]][a.num[5]] = true;
    while (!q.empty())
    {
        x = q.front();
        q.pop();
        if (Mycmp(x, b))
        {
            printf("%d\n", x.step);
            return;
        }

        //以下是四种操作
        if (!vis[x.num[4]][x.num[5]][x.num[2]][x.num[3]][x.num[1]][x.num[0]])
        {
            vis[x.num[4]][x.num[5]][x.num[2]][x.num[3]][x.num[1]][x.num[0]] = true;
            y = x;
            y.num[0] = x.num[4];
            y.num[1] = x.num[5];
            y.num[4] = x.num[1];
            y.num[5] = x.num[0];
            y.step++;
            q.push(y);
        }
        if (!vis[x.num[5]][x.num[4]][x.num[2]][x.num[3]][x.num[0]][x.num[1]])
        {
            vis[x.num[5]][x.num[4]][x.num[2]][x.num[3]][x.num[0]][x.num[1]] = true;
            y = x;
            y.num[0] = x.num[5];
            y.num[1] = x.num[4];
            y.num[4] = x.num[0];
            y.num[5] = x.num[1];
            y.step++;
            q.push(y);
        }
        if (!vis[x.num[3]][x.num[2]][x.num[0]][x.num[1]][x.num[4]][x.num[5]])
        {
            vis[x.num[3]][x.num[2]][x.num[0]][x.num[1]][x.num[4]][x.num[5]] = true;
            y = x;
            y.num[0] = x.num[3];
            y.num[1] = x.num[2];
            y.num[2] = x.num[0];
            y.num[3] = x.num[1];
            y.step++;
            q.push(y);
        }
        if (!vis[x.num[2]][x.num[3]][x.num[1]][x.num[0]][x.num[4]][x.num[5]])
        {
            vis[x.num[2]][x.num[3]][x.num[1]][x.num[0]][x.num[4]][x.num[5]] = true;
            y = x;
            y.num[0] = x.num[2];
            y.num[1] = x.num[3];
            y.num[2] = x.num[1];
            y.num[3] = x.num[0];
            y.step++;
            q.push(y);
        }
    }
    puts("-1");     //无法到达目标状态
    return;
}

bool Mycmp(dice x, dice y)
{
    for (int i=0; i<6; ++i)
    {
        if (x.num[i] != y.num[i])
        {
            return false;
        }
    }
    return true;
}