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 ;

 }

BFS POJ 2251 Dungeon Master的相关教程结束。