题意分析

给一个由数字组成的地图和一个设定好的骰子。骰子被放在一个地点，告诉你地点的坐标和此时骰子的上面和前面。要求是当骰子的上面的值等于骰子周围点的值 或者 周围有一个-1的值的时候才能把骰子移动到那边。最后要求出骰子返回初始位置的路径。

解题思路

首先骰子是给定的，所以知道上面和正面的时候我们就能知道骰子的各个面了，因为骰子的正对的两个面的值之和是7.。然后用一个4维的数组判重，一二维度记录坐标。第三维记录上面的值，第四维记录正面的值。然后进行BFS。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>

using namespace std;

struct node
{
    int x, y;
    int up;
    int f;
    vector <int> path;
};

int map[12][12];
int v[12][12][7][7];
int state[7][7];
int dx[] = { -1,1,0,0 };  //题目要求的是按上下左右的最小字典序
int dy[] = { 0,0,-1,1 };
int n, m;
int stx, sty;

void bfs(node t)
{
    queue<node>Q;
    node w, e;
    Q.push(t);

    while (!Q.empty())
    {
        w = Q.front();
        Q.pop();

        for (int k = 0; k < 4; k++)
        {
            e = w;
            int x = e.x + dx[k];
            int y = e.y + dy[k];
            int tf = e.f, tup = e.up;

            if (k == 0) { tf = 7 - e.up; tup = e.f; }//往上翻
            else if (k == 1) { tup = 7 - e.f; tf = e.up; } //往下翻
            else if (k == 2)tup = state[e.up][e.f];//....
            else tup = 7 - state[e.up][e.f]; //....

            if (map[x][y] != 0 && (map[x][y] == e.up || map[x][y] == -1) && v[x][y][tup][tf] == 0)
            {
                //printf("x = %d y = %d up = %d f = %d\n",x,y,tup,tf);
                v[x][y][tup][tf] = 1;
                e.x = x;
                e.y = y;
                e.f = tf;
                e.up = tup;
                e.path.push_back(x);
                e.path.push_back(y);
                Q.push(e);

                if (x == stx && y == sty)
                {
                    // printf("  ");
                    for (int s = 0; s < e.path.size() / 2; s++)  //注意打印的格式控制
                    {
                        if (s % 9 == 0)printf("  ");
                        if (s != e.path.size() / 2 - 1)printf("(%d,%d),", e.path[s * 2], e.path[s * 2 + 1]);
                        else printf("(%d,%d)", e.path[s * 2], e.path[s * 2 + 1]);

                        if ((s + 1) % 9 == 0 && s != e.path.size() / 2 - 1)printf("\n");

                    }
                    return;
                }
            }
        }
    }
    printf("  No Solution Possible");
}


int main()
{
    memset(state, 0, sizeof(state));
    state[1][2] = 3; state[1][3] = 5; state[1][4] = 2; state[1][5] = 4;   //首先处理骰子的状态
    state[2][1] = 4; state[2][4] = 6; state[2][6] = 3; state[2][3] = 1;
    state[3][1] = 2; state[3][2] = 6; state[3][6] = 5; state[3][5] = 1;
    state[4][1] = 5; state[4][5] = 6; state[4][6] = 2; state[4][2] = 1;
    state[5][1] = 3; state[5][3] = 6; state[5][6] = 4; state[5][4] = 1;
    state[6][2] = 4; state[6][4] = 5; state[6][5] = 3; state[6][3] = 2;

    string name;
    node w;
    while (cin >> name)
    {
        if (name == "END")break;

        memset(map, 0, sizeof(map));
        memset(v, 0, sizeof(v));
        w.path.clear();
        scanf("%d%d%d%d%d%d", &n, &m, &w.x, &w.y, &w.up, &w.f);

        stx = w.x;
        sty = w.y;

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                scanf("%d", &map[i][j]);

        w.path.push_back(w.x);
        w.path.push_back(w.y);

        cout << name << endl;

        bfs(w);
        putchar(10);
    }
    return 0;
}