首页 > 代码库 > 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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。