题目描述：https://uva.onlinejudge.org/external/8/810.pdf
把一个骰子放在一个M x N的地图上，让他按照规定滚动，求滚回原点的最短路径。
思路: 记忆化搜索(我这里用的dfs深度优先搜索)
难点：
如何推导骰子的状态
我没有用打表，而是先用build_dice()初始化二维数组dice， 这样，当我们有骰子的顶面top，正面face, 就可以通过dice[top][face] 获得对应的右面，由此，就可以实现骰子的旋转。rotate()函数实现骰子的旋转，给它top, face, 和旋转的方向(前，后，左，右)， 它会返回旋转后骰子的top, face.
记忆化搜索要多一个状态记录骰子的状态
说白了就是记录访问状态的数组vis要多两个维度分别记录top, face，因为top, face一旦固定，骰子就固定了
Note: 输出的格式也要稍微注意一下，锁进、末尾的逗号，换行要处理好。
#include <iostream>
#include <cstdio>
#include <vector>
#include <utility>
#include <cstring>
using namespace std;
const int MAXN = + ;
int b[MAXN][MAXN], R, C, sx, sy, st, sf, len;
int dx[] = {, -, , }, dy[] = {, , -, }, dice[][];
bool vis[MAXN][MAXN][][], ok, first;
vector<pair<int, int> > path;
void build_dice() { //dice[top][face] = right
dice[][] = ;
for (int i = ; i < ; i++) {
for (int j = ; j < ; j++) {
if (i == j) continue;
if (dice[i][ - j]) dice[i][j] = - dice[i][ - j];
if (dice[i][j]) {
dice[j][i] = - dice[i][j];
dice[i][dice[i][j]] = - j;
}
}
}
}
pair<int, int> rotate(int top, int face, int di) {
pair<int, int> n_tf;
if (di == ) {
n_tf.second = face;
n_tf.first = - dice[top][face];
}
else if (di == ) {
n_tf.first = face;
n_tf.second = - top;
}
else if (di == ) {
n_tf.second = face;
n_tf.first = dice[top][face];
}
else {
n_tf.second = top;
n_tf.first = - face;
}
return n_tf;
}
bool inside(int x, int y) {
return x > && y > && x <= R && y <= C;
}
void dfs(int x, int y, int t, int f) {
path.push_back(make_pair(x, y));
if (x == sx && y == sy)
if (first) first = ;
else { ok = ; return;}
vis[x][y][t][f] = ;
for (int i = ; i < ; i++) {
pair<int, int> nextp = rotate(t, f, i);
int nx = x + dx[i], ny = y + dy[i];
int nt = nextp.first, nf = nextp.second;
if (inside(nx, ny) && (!vis[nx][ny][nt][nf] || (nx == sx && ny == sy)) && (t == b[nx][ny] || b[nx][ny] == -)) {
dfs(nx, ny, nt, nf);
}
if (ok) return;
}
vis[x][y][t][f] = ;
path.pop_back();
}
int main() {
build_dice();
char name[];
while (scanf("%s", name) == && strcmp(name, "END")) {
scanf("%d%d%d%d%d%d", &R, &C, &sx, &sy, &st, &sf);
memset(vis, , sizeof(vis));
memset(b, , sizeof(b));
path.clear(); ok = ; first = ;
for (int i = ; i <= R; i++)
for (int j = ; j <= C; j++)
scanf("%d", &b[i][j]);
dfs(sx, sy, st, sf);
len = path.size();
printf("%s", name);
if (ok)
for (int i = ; i < len; i++) {
if (i % == ) {
if (i >= ) printf(",");
printf("\n (%d,%d)", path[i].first, path[i].second);
}
else printf(",(%d,%d)", path[i].first, path[i].second);
}
else printf("\n No Solution Possible");
printf("\n");
}
return ;
}