poj2251 Dungeon Master

题目：

Description
You are trapped in a 3D dungeon and need to find the quickest way out! The dungeon is composed of unit cubes which may or may not be filled with rock. It takes one minute to move one unit north, south, east, west, up or down. You cannot move diagonally and the maze is surrounded by solid rock on all sides. Is an escape possible? If yes, how long will it take?
Input
The input consists of a number of dungeons. Each dungeon description starts with a line containing three integers L, R and C (all limited to 30 in size). L is the number of levels making up the dungeon. R and C are the number of rows and columns making up the plan of each level. Then there will follow L blocks of R lines each containing C characters. Each character describes one cell of the dungeon. A cell full of rock is indicated by a '#' and empty cells are represented by a '.'. Your starting position is indicated by 'S' and the exit by the letter 'E'. There's a single blank line after each level. Input is terminated by three zeroes for L, R and C.
Output
Each maze generates one line of output. If it is possible to reach t
he exit, print a line of the form Escaped in x minute(s).
where x is replaced by the shortest time it takes to escape. If it is not possible to escape, print the line Trapped!

poj2251.PNG

题目大意：
有一个地牢，分为L层，每层R行C列。有一个人从起点出发，可以在同层上下左右移动，也可以到底层的同行同列处，也可以到高层的同行同列出（空间的前后左右上下）。'.'表示可以通过，'#'表示不能通过。问他能否到达终点，能则输出时间，否则输出"Trapped!"。

其实这道题可以用BFS过，只不过是空间六个方向。

参考代码：

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 50+5;
const int M = 30000+10;

int diry[6] = {-1, 0, 0, 1, 0, 0};//方向坐标(前四个);
int dirz[6] = {0, 1, -1, 0, 0, 0};//组合起来分别代表上右左下(前四个);
int dirx[6] = {0, 0, 0, 0, 1, -1};//空间的下与上;
int L, R, C;
char map[N][N][N];
bool vis[N][N][N];
struct node {
    int x, y, z;//记录该点的位置;
    int times;//记录当前已用的时间;
} que[M];

void init() {
    for (int i = 0;i < L;++i) {
        for (int j = 0;j < R;++j) {
            for (int k = 0;k < C;++k) {
                map[i][j][k] = '#';
            }
        }
    }
    memset(que, 0, sizeof(que));
    memset(vis, false, sizeof(vis));
}

node s;
void input() {
    for (int i = 0;i < L;++i) {
        for (int j = 0;j < R;++j) {
            cin >> map[i][j];
            for (int k = 0;k < C;++k) {
                if (map[i][j][k] == 'S') {
                    s.x = i;
                    s.y = j;
                    s.z = k;
                    s.times = 0;
                    vis[i][j][k] = true;    
                }
            }
        }
    }
}

void bfs() {
    int l = 0, r = 0;
    que[r++] = s;
    node p;
    bool flag = false;
    while (r > l) {//队列不为空;
        p = que[l++];
        if (map[p.x][p.y][p.z] == 'E') {//已经到达终点;
            flag = true;
            cout << "Escaped in " << p.times << " " << "minute(s)" << "." << endl; 
            break;
        }
        node q;
        for (int i = 0;i < 6;++i) {
            int nx, ny, nz;
            nx = p.x + dirx[i];
            ny = p.y + diry[i];
            nz = p.z + dirz[i]; 
            if (nx >= 0 && nx < L && ny >= 0 && ny < R && nz >= 0 && nz < C && map[nx][ny][nz] != '#' && !vis[nx][ny][nz]) {
                q.x = nx;
                q.y = ny;
                q.z = nz;
                q.times = p.times + 1;
                que[r++] = q;
                vis[nx][ny][nz] = true;         
            }       
        }   
    }
    if (!flag)
        cout << "Trapped!" << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    while (cin >> L >> R >> C) {
        if (L == 0 && R == 0 && C == 0) break;
        cin.get();
        init();
        input();
        bfs();
    }
    return 0;
}