poj-2251

//788K  0MS G++#include <cstdio>#include <queue>#include <cstring>#define MAX 50using namespace std;char maze[MAX][MAX][MAX]; // z , y, xstruct Pos {    int x;    int y;    int z;    int time;};typedef struct Pos Pos;queue<Pos> BFSQueue;char BFSFlag[MAX][MAX][MAX];using namespace std;int W;int H;int C; // the level num of mazeint Sx;int Sy;int Sz;int Ex;int Ey;int Ez;char checkNode(int curX, int curY, int curZ, int curTime) {    BFSFlag[curX][curY][curZ] = 1;    Pos newPos;    if (curX == Ex && curY == Ey && curZ == Ez) {        return curTime + 1;    }    newPos.x = curX;    newPos.y = curY;    newPos.z = curZ;    newPos.time = curTime + 1;    BFSQueue.push(newPos);    return 0;}int BFS() {    while(BFSQueue.size()) {        BFSQueue.pop();    }    memset(BFSFlag, 0, sizeof(BFSFlag));    Pos beginPos;    beginPos.x = Sx;    beginPos.y = Sy;    beginPos.z = Sz;    beginPos.time = 0;    BFSFlag[Sx][Sy][Sz] = 1;    BFSQueue.push(beginPos);    while(BFSQueue.size()) {        Pos curPos = BFSQueue.front();        BFSQueue.pop();        int curX = curPos.x;        int curY = curPos.y;        int curZ = curPos.z;        int curTime = curPos.time;        //head top        if (curZ + 1 <= C-1 &&            maze[curZ+1][curY][curX] != '#' &&            !BFSFlag[curX][curY][curZ+1]) {            if (checkNode(curX, curY, curZ+1, curTime)) {                return curTime + 1;            }        }        //under foot        if (curZ > 0 &&            maze[curZ-1][curY][curX] != '#' &&            !BFSFlag[curX][curY][curZ-1]) {            if (checkNode(curX, curY, curZ-1, curTime)) {                return curTime + 1;            }        }        // front        if (curY +1 <= H-1 &&            maze[curZ][curY+1][curX] != '#' &&            !BFSFlag[curX][curY+1][curZ]) {            if (checkNode(curX, curY+1, curZ, curTime)) {                return curTime + 1;            }        }        // back        if (curY > 0 &&            maze[curZ][curY-1][curX] != '#' &&            !BFSFlag[curX][curY-1][curZ]) {            if (checkNode(curX, curY-1, curZ, curTime)) {                return curTime + 1;            }        }        // left        if (curX > 0 &&            maze[curZ][curY][curX-1] != '#' &&            !BFSFlag[curX-1][curY][curZ]) {            if (checkNode(curX-1, curY, curZ, curTime)) {                return curTime + 1;            }        }        //right        if (curX + 1 <= W-1 &&            maze[curZ][curY][curX+1] != '#' &&            !BFSFlag[curX+1][curY][curZ]) {            if (checkNode(curX+1, curY, curZ, curTime)) {                return curTime + 1;            }        }    }    return -1; // trapped!}void solve() {    int res = BFS();    if (res == -1) {        printf("Trapped!\n");    } else {        printf("Escaped in %d minute", res);        if (res > 1) {            printf("(s).\n");        } else {            printf(".\n");        }    }}int main () {    while(1) {        scanf("%d %d %d", &C, &H, &W);        if (C == 0 && H ==0 && W ==0) {            return 0;        }        for (int i = 0; i < C; i++) {            for (int j = 0; j < H; j++) {                scanf("%s", maze[i][j]);                for (int k = 0; k < W; k++) {                    if (maze[i][j][k] == 'S') {                        Sz = i;                        Sy = j;                        Sx = k;                    } else if (maze[i][j][k] == 'E') {                        Ez = i;                        Ey = j;                        Ex = k;                    }                }            }        }        solve();    }}

一个变种迷宫最短的路径问题，不同的是，从2D迷宫到3D迷宫，除了四个二维方向，增加了头部和脚的两个方向，其他方向没有改变，

或者直接BFS求(但分类这个问题在DFS， DFS可以解决，但是效率明显不高，这个问题的状态保存只有三个坐标，没有状态保存不好的问题)

描述迷宫的数组也从二维数组变为三维数组，直接用三维字符数组maze保存，但坐标对应 maze[z][y][x]， 其他的都一样。