学步园

(原题：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=10&page=show_problem&problem=751 
)

感觉这道题和例题6-14 Abott's Revenge很像，都是在图的bfs求最短路的基础上增加了一个维度。在Abott's Revenge中，增加的维度是前进的方向，而这道题增加的维度则是色子的形态。

我把色子的六个面按照如下的顺序编号（图片借用了UVa#253 习题4-4 Cube Paiting），然后用一个int数组保存。例如当前的色子表示为1 2 3 4 5 6，向右旋转后则变为3 2 6 1 5 4。

其他的地方则是普通的bfs，中间需要注意一些细节：

1、maze坐标是从1开始

2、色子旋转的函数要测试正确性

3、色子最初形态的初始化的方法

4、判断当前状态是否曾经访问过的方法

一开始给色子初始化的时候伤了脑筋，中间的很多细节问题也导致了较长时间的debug。。不过很开心一次就AC了

还有内存泄露的问题没有解决，另外不太清楚如果不用指针的话应该怎么做

Run Time: 0.026s

//  UVa   #6-12.810.cpp

#include<iostream>
#include<stack>
#include<vector>
#include<queue>
#include<cstring>
#include<cstdlib>
#include<cstdio>

using namespace std;

#define maxn 20

struct State {              //色子的状态，包括色子的位置和形态
    int r, c;
    int dice[6];
    State* father;          //bfs最短路父节点
    State(int x, int y) {
        r = x; c = y;
        for(int i = 0; i < 6; i ++) dice[i] = i+1;
        father = NULL;
    }
    State(int x, int y, int* a) {
        r = x; c = y;
        for(int i = 0; i < 6; i ++) dice[i] = a[i];
        father = NULL;
    }
};


//Global Variable
int step[2][4] = {{-1,0,1,0},{0,1,0,-1}};           //step用于走路。step[0]对应行的变化，step[1]对应列的变化。0为向上，之后1,2,3按顺时针顺序
int m, n, startR, startC, startTop, startFront;
int maze[maxn][maxn];
/////

void swap(State* s, int a, int b);
void rot(State* s, int d);              //旋转色子
void initiate(State* s);                //将色子置为题目给出的形态
int inside(int x, int y);               //判断是否在maze内
int statecmp(State* s1, State* s2);     //比较两个状态是否相同(也可重载State的==操作符)
State* solve(State* startS);            //主逻辑，bfs
void print_ans(State* endS);            //打印解

int main() {
    char name[50];
    while(scanf("%s", name) && strcmp(name, "END")) {
        scanf("%d%d%d%d%d%d", &m, &n, &startR, &startC, &startTop, &startFront);
        memset(maze, 0, sizeof(maze));
        for(int i = 1; i <= m; i ++) for(int j = 1; j <= n; j ++) scanf("%d", &maze[i][j]);
//        if(startTop + startFront == 7) {
//            printf("%s\n  No Solution Possible\n", name);         //如果题目给出了一种不可能出现的dice config，这里可以直接判否。但是本题不用这个判断也可以AC
//            continue;
//        }
        State* startS = new State(startR, startC);
        initiate(startS);

        printf("%s\n", name);
        print_ans(solve(startS));
        //这里有内存泄露，可以用内存池来解决。
    }

    return 0;
}

void rot(State* s, int d) {
    switch(d) {
    case 0:
        swap(s, 0, 1);
        swap(s, 4, 5);
        swap(s, 1, 4);
        break;
    case 1:
        swap(s, 0, 2);
        swap(s, 3, 5);
        swap(s, 0, 5);
        break;
    case 2:
        swap(s, 1, 4);
        swap(s, 0, 1);
        swap(s, 4, 5);
        break;
    case 3:
        swap(s, 0, 2);
        swap(s, 3, 5);
        swap(s, 2, 3);
        break;
    case 4:
        swap(s, 1, 2);
        swap(s, 3, 4);
        swap(s, 1, 4);
        break;
    }
}

void initiate(State* s) {
    for(int i = 0; i < 4; i ++) {
        if(s->dice[0] == startTop) break;
        rot(s, 0);
    }
    for(int i = 0; i < 4; i ++) {
        if(s->dice[0] == startTop) break;
        rot(s, 1);
    }
    //上面分别按x轴和y轴旋转，直到达到题目要求的top面
    for(int i = 0; i < 4; i ++) {
        if(s->dice[1] == startFront) break;
        rot(s,4);
    }
    //按z轴旋转，直到达到题目要求的冲着自己的(front)面
}
void swap(State* s, int a, int b) {
    int tmp = s->dice[a];
    s->dice[a] = s->dice[b];
    s->dice[b] = tmp;
}
int inside(int x, int y) {
    if(x < 1 || x > m || y < 1 || y > n) return 0; return 1;
}
int statecmp(State* s1, State* s2) {
    if(s1->r != s2->r || s1->c != s2->c) return 0;
    for(int i = 0; i < 6; i ++)
        if((s1->dice)[i] != (s2->dice)[i]) return 0;
    return 1;
}

State* solve(State* startS) {           //BFS
    vector<State*> vis;
    queue<State*> q;
    q.push(startS);
    int moveflag = 0;                   //避免一开始就判断为抵达
    while(!q.empty()) {
        State* curS = q.front(); q.pop();
        int curR = curS->r, curC = curS->c;

        if(curR == startR && curC == startC && moveflag) return curS;       //抵达目的地

        int flag = 0;
        for(int i = 0; i < vis.size(); i ++)
            if(statecmp(vis[i], curS)) {
                flag = 1;
                break;
            }
        if(flag) continue;              //若之前到达过这个状态则不往下继续。这里用map会比较快，但是要定义State的小于号操作符。鉴于状态的可能性不算多(10^2级)，这里就不做优化了
        vis.push_back(curS);

        for(int i = 0; i < 4; i ++) {
            int newR = curR + step[0][i], newC = curC + step[1][i];
            if(inside(newR, newC) && (maze[newR][newC] == curS->dice[0] || maze[newR][newC] == -1)) {
                State* newS = new State(newR, newC, curS->dice);        //再次：这里应该用内存池解决泄露
                rot(newS, i);
                newS->father = curS;
                q.push(newS);
                moveflag = 1;
            }
        }
    }
    return NULL;
}

void print_ans(State* endS) {
    if(endS == NULL) {
        printf("  No Solution Possible\n");
        return;
    }
    State* curS = endS;
    stack<pair<int,int> > s;
    while(curS != NULL) {
        s.push(pair<int,int>(curS->r, curS->c));
        curS = curS->father;
    }
    int cnt = 0;
    printf("  ");
    while(1) {
        printf("(%d,%d)", s.top().first, s.top().second);
        s.pop();
        if(!s.empty()){
            printf(",");
            if((++cnt)%9 == 0) {
                printf("\n");
                printf("  ");
            }
        }
        else {
            printf("\n");
            break;
        }
    }
}