POJ 2251 Dungeon Master：三維迷宮 BFS 逃脫

題目描述

三維地牢 L×R×C（≤30），S 起點，E 終點，# 岩石，. 空地。六個方向移動，每步 1 分鐘。求最短逃脫時間或 "Trapped!"。

解題思路：標準三維 BFS

1. 讀入地圖，記錄起點 (sx,sy,sz) 和終點 (ex,ey,ez)。注意輸入順序：層、行、列，對應數組 map[z][y][x]。
2. BFS 隊列存 (x,y,z,dist)。六方向向量：(±1,0,0), (0,±1,0), (0,0,±1)。
3. 訪問標記直接修改 map 為 '#' 或單獨 vis 數組。
4. 到達終點返回距離，隊列空返回 0（Trapped）。

C++ 代碼實現

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

struct Node { int x, y, z, d; };
char map[35][35][35];
int L, R, C;
int dx[6] = {1,-1,0,0,0,0};
int dy[6] = {0,0,1,-1,0,0};
int dz[6] = {0,0,0,0,1,-1};

int bfs(int sx, int sy, int sz, int ex, int ey, int ez) {
    queue q;
    q.push({sx, sy, sz, 0});
    map[sz][sy][sx] = '#'; // 標記訪問
    while (!q.empty()) {
        Node cur = q.front(); q.pop();
        if (cur.x == ex && cur.y == ey && cur.z == ez) return cur.d;
        for (int i = 0; i < 6; ++i) {
            int nx = cur.x + dx[i], ny = cur.y + dy[i], nz = cur.z + dz[i];
            if (nx>=0 && nx=0 && ny=0 && nz