首页 > 代码库 > POJ 2251 Dungeon Master(三维空间bfs)

POJ 2251 Dungeon Master(三维空间bfs)

题意:三维空间求最短路,可前后左右上下移动。

分析:开三维数组即可。

#include<cstdio>#include<cstring>#include<queue>using namespace std;const int MAXN = 30 + 10;char pic[MAXN][MAXN][MAXN];bool vis[MAXN][MAXN][MAXN];int sx, sy, sz;int dr[] = {0, 0, 1, -1, 0, 0};int dc[] = {1, -1, 0, 0, 0, 0};int dz[] = {0, 0, 0, 0, 1, -1};int L, R, C;bool judge(int x, int y, int z){    return x >= 0 && x < R && y >= 0 && y < C && z >= 0 && z < L;}int bfs(){    queue<int> x, y, z, step;    x.push(sx), y.push(sy), z.push(sz), step.push(0);    vis[sz][sx][sy] = true;    while(!x.empty()){        int tmpx = x.front(); x.pop();        int tmpy = y.front(); y.pop();        int tmpz = z.front(); z.pop();        int tmpstep = step.front(); step.pop();        for(int i = 0; i < 6; ++i){            int tx = tmpx + dr[i];            int ty = tmpy + dc[i];            int tz = tmpz + dz[i];            if(judge(tx, ty, tz)){                if(pic[tz][tx][ty] == ‘E‘) return tmpstep + 1;                if(pic[tz][tx][ty] != ‘#‘ && !vis[tz][tx][ty]){                    vis[tz][tx][ty] = true;                    x.push(tx);                    y.push(ty);                    z.push(tz);                    step.push(tmpstep + 1);                }            }        }    }    return -1;}int main(){    while(scanf("%d%d%d", &L, &R, &C) == 3){        if(!L && !R && !C) return 0;        memset(vis, false, sizeof vis);        for(int i = 0; i < L; ++i){            for(int j = 0; j < R; ++j){                scanf("%s", pic[i][j]);                for(int k = 0; k < C; ++k){                    if(pic[i][j][k] == ‘S‘){                        sz = i, sx = j, sy = k;                    }                }            }        }        int ans = bfs();        if(ans == -1) printf("Trapped!\n");        else printf("Escaped in %d minute(s).\n", ans);    }    return 0;}

  

POJ 2251 Dungeon Master(三维空间bfs)