POJ 2251 Dungeon Master

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <queue>
  4 using namespace std;
  5 
  6 struct Piont{
  7     int x;
  8     int y;
  9     int z;
 10     Piont(int x, int y, int z) :x(x), y(y), z(z){};
 11 };
 12 
 13 typedef Piont P;
 14 const int INF = 100000000;
 15 char m[35][35][35];
 16 int d[35][35][35];
 17 int dx[6] = { 1, -1, 0, 0, 0, 0 };
 18 int dy[6] = { 0, 0, 1, -1, 0, 0 };
 19 int dz[6] = { 0, 0, 0, 0, 1, -1 };
 20 
 21 int main()
 22 {
 23     int L, R, C, time, temp;
 24     int Sx, Sy, Sz, Ex, Ey, Ez;
 25 
 26     while (scanf("%d%d%d", &L, &R, &C) != EOF && L && R && C)
 27     {
 28         getchar();
 29         memset(m, 0, sizeof(m));
 30         for (int i = 0; i<L; i++)
 31         {
 32             for (int j = 0; j<R; j++)
 33             {
 34                 for (int k = 0; k<C; k++)
 35                 {
 36                     scanf("%c", &m[i][j][k]);
 37                     if (m[i][j][k] == ‘S‘)
 38                     {
 39                         Sx = i; Sy = j; Sz = k;
 40                     }
 41                     if (m[i][j][k] == ‘E‘)
 42                     {
 43                         Ex = i; Ey = j; Ez = k;
 44                     }
 45                 }
 46                 getchar();
 47             }
 48             getchar();
 49         }
 50 
 51         /*
 52         for (int i = 0; i<L; i++)
 53         {
 54             for (int j = 0; j<R; j++)
 55             {
 56                 for (int k = 0; k < C; k++)
 57                 {
 58                     printf("%d%c ",k, m[i][j][k]);
 59                 }
 60                 printf("\n");
 61             }
 62             
 63         }
 64         */
 65         
 66         for (int i = 0; i<L; i++)
 67             for (int j = 0; j<R; j++)
 68                 for (int k = 0; k < C; k++)
 69                     d[i][j][k] = INF;
 70 
 71         queue<P> q;
 72         q.push(P(Sx, Sy, Sz));
 73         d[Sx][Sy][Sz] = 0;
 74         
 75         while (q.size())
 76         {
 77             P p = q.front();
 78             q.pop();
 79             if (p.x == Ex && p.y == Ey && p.z == Ez)
 80                 break;
 81             for (int i = 0; i < 6; i++)
 82             {
 83                 int nx = p.x + dx[i];
 84                 int ny = p.y + dy[i];
 85                 int nz = p.z + dz[i];
 86 
 87                 if (0 <= nx&&nx < L && 0 <= ny&&ny < R && 0 <= nz&&nz < C
 88                     && m[nx][ny][nz] != ‘#‘&&d[nx][ny][nz]==INF)
 89                 {
 90                     q.push(P(nx, ny, nz));
 91                     d[nx][ny][nz] = d[p.x][p.y][p.z] + 1;
 92                 }
 93             }
 94         }
 95 
 96         if (d[Ex][Ey][Ez]!=INF)
 97         {
 98             printf("Escaped in %d minute(s).\n", d[Ex][Ey][Ez]);
 99         }
100         else
101         {
102             printf("Trapped!\n");
103         }
104         
105     }
106 }