BFS POJ 2251 Dungeon Master

题目传送门

 /*
BFS:这题很有意思,像是地下城,图是立体的,可以从上张图到下一张图的对应位置,那么也就是三维搜索,多了z坐标轴
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std; const int MAXN = ;
const int INF = 0x3f3f3f3f;
struct Point {
int x, y, z, step;
};
char maze[MAXN][MAXN][MAXN];
int dx[] = {-, , , , , };
int dy[] = {, , -, , , };
int dz[] = {, , , , -, };
bool vis[MAXN][MAXN][MAXN];
int l, r, c; bool judge(int x, int y, int z) {
if (x < || x > r || y < || y > c || z < || z > l || vis[z][x][y] || maze[z][x][y] == '#') return false;
return true;
} void BFS(void) {
int sx, sy, sz, ex, ey, ez;
for (int i=; i<=l; ++i) {
for (int j=; j<=r; ++j) {
for (int k=; k<=c; ++k) {
if (maze[i][j][k] == 'S') {
sx = j; sy = k; sz = i;
}
else if (maze[i][j][k] == 'E') {
ex = j; ey = k; ez = i;
}
}
}
}
memset (vis, false, sizeof (vis));
queue<Point> Q; Q.push ((Point) {sx, sy, sz, });
bool flag = false; vis[sz][sx][sy] = true;
while (!Q.empty ()) {
Point p = Q.front (); Q.pop ();
if (p.x == ex && p.y == ey && p.z == ez) {
printf ("Escaped in %d minute(s).\n", p.step);
flag = true; break;
}
for (int i=; i<; ++i) {
int tx = p.x + dx[i]; int ty = p.y + dy[i]; int tz = p.z + dz[i];
if (judge (tx, ty, tz)) {
vis[tz][tx][ty] = true;
Q.push (Point {tx, ty, tz, p.step + });
}
}
}
if (!flag) puts ("Trapped!");
} int main(void) { //POJ 2251 Dungeon Master
while (scanf ("%d%d%d", &l, &r, &c) == ) {
if (!l && !r && !c) break;
for (int i=; i<=l; ++i) {
for (int j=; j<=r; ++j) scanf ("%s", maze[i][j] + );
}
BFS ();
} return ;
}
上一篇:Linux PS 命令详解


下一篇:POJ 2251 Dungeon Master --- 三维BFS(用BFS求最短路)