POJ 2251 Dungeon Master （非三维bfs）

Dungeon Master

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 55224		Accepted: 20493

Description

You are trapped in a 3D dungeon and need to find the quickest way out! The dungeon is composed of unit cubes which may or may not be filled with rock. It takes one minute to move one unit north, south, east, west, up or down. You cannot move diagonally and the maze is surrounded by solid rock on all sides.

Is an escape possible? If yes, how long will it take?

Input

The input consists of a number of dungeons. Each dungeon description starts with a line containing three integers L, R and C (all limited to 30 in size).
L is the number of levels making up the dungeon.
R and C are the number of rows and columns making up the plan of each level.
Then there will follow L blocks of R lines each containing C characters. Each character describes one cell of the dungeon. A cell full of rock is indicated by a '#' and empty cells are represented by a '.'. Your starting position is indicated by 'S' and the exit by the letter 'E'. There's a single blank line after each level. Input is terminated by three zeroes for L, R and C.

Output

Each maze generates one line of output. If it is possible to reach the exit, print a line of the form

Escaped in x minute(s).

where x is replaced by the shortest time it takes to escape.
If it is not possible to escape, print the line

Trapped!

Sample Input

3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0

Sample Output

Escaped in 11 minute(s).
Trapped!

思路：看了网上很多人用的都是三维的bfs，但是此题可以用二维解决。 向上或向下走时，只要令x坐标减去或加上R即可，要注意的就是往东西南北方向走时不能越层，而只能在同一层走。
　　　输入中的换行可以无视。

当时做的时候找错找了好久，最后发现是for循环里面的t.y写成了t.x，我晕~  ---->>>> 以后写代码时一定要细心(ノ▼Д▼)ノ

  1 #include<iostream>  
  2 #include<cstring>   //使用memset必须加此头文件
  3 #include<stdio.h>　 //使用printf必须加此头文件
  4 #include<queue>
  5 
  6 using namespace std;
  7 
  8 int L, R, C;
  9 int minute = 0;
 10 char maze[1000][1000];
 11 int vis[1000][1000];
 12 int dx[] = { 1,-1,0,0 };    //南北方向
 13 int dy[] = { 0,0,1,-1 };    //东西方向
 14 
 15 struct node
 16 {
 17     int x, y;
 18     int step;
 19 }s;
 20 
 21 void bfs(int x, int y)
 22 {
 23     s.x = x;
 24     s.y = y;
 25     s.step = 0;
 26     vis[x][y] = 1;
 27     queue<node> Q;
 28     Q.push(s);
 29 
 30     node t;
 31     while (!Q.empty())
 32     {
 33         t = Q.front();
 34         Q.pop();
 35 
 36         if (maze[t.x][t.y] == 'E')
 37         {
 38             printf("Escaped in %d minute(s).
", t.step);
 39             return;
 40         }
 41 
 42         // k表示此坐标所在的层数，因为如果只是往东西南北方向走的话，只能在同一层
 43         int k = t.x / R + 1;
 44 
 45         for (int i = 0; i < 4; ++i)
 46         {
 47             int xx = t.x + dx[i];
 48             int yy = t.y + dy[i];
 49 
 50             //注意同一层中的坐标判断条件
 51             if ((xx >= ((k - 1)*R)) && (xx < (k*R)) && yy >= 0 & yy < C && maze[xx][yy] != '#' && !vis[xx][yy])
 52             {
 53                 vis[xx][yy] = 1;
 54                 s.x = xx;
 55                 s.y = yy;
 56                 s.step = t.step + 1;
 57                 Q.push(s);
 58             }
 59         }
 60 
 61         //跳入下一层
 62         int x1 = t.x + R;
 63         int y1 = t.y;
 64         if (x1 < L*R && maze[x1][y1] != '#' && !vis[x1][y1])
 65         {
 66             vis[x1][y1] = 1;
 67             s.x = x1;
 68             s.y = y1;
 69             s.step = t.step + 1;
 70             Q.push(s);
 71         }
 72 
 73         //跳入上一层
 74         int x2 = t.x - R;
 75         int y2 = t.y;
 76         if (x2 >= 0 && maze[x2][y2] != '#' && !vis[x2][y2])
 77         {
 78             vis[x2][y2] = 1;
 79             s.x = x2;
 80             s.y = y2;
 81             s.step = t.step + 1;
 82             Q.push(s);
 83         }
 84     }
 85 
 86     cout << "Trapped!" << endl;
 87 
 88 }
 89 
 90 int main()
 91 {
 92     int start_x, start_y;    //记录起点坐标
 93     while (cin >> L >> R >> C)
 94     {
 95         if (L == 0 && R == 0 && C == 0)
 96             break;
 97 
 98         for (int i = 0; i < L*R; ++i)
 99             for (int j = 0; j < C; ++j)
100             {
101                 cin >> maze[i][j];    //迷宫下标从0开始存储
102                 if (maze[i][j] == 'S')
103                 {
104                     start_x = i;
105                     start_y = j;
106                 }
107             }
108 
109         memset(vis, 0, sizeof(vis));
110         bfs(start_x, start_y);
111 
112     }
113     return 0;
114 }