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 5S.....###..##..###.#############.####...###########.#######E1 3 3S###E####0 0 0
Sample Output
Escaped in 11 minute(s).Trapped! 思路：看了网上很多人用的都是三维的bfs，但是此题可以用二维解决。 向上或向下走时，只要令x坐标减去或加上R即可，要注意的就是往东西南北方向走时不能越层，而只能在同一层走。 输入中的换行可以无视。 当时做的时候找错找了好久，最后发现是for循环里面的t.y写成了t.x，我晕~ ---->>>> 以后写代码时一定要细心(ノ▼Д▼)ノ
1 #include2 #include //使用memset必须加此头文件 3 #include //使用printf必须加此头文件 4 #include 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 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).\n", 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 }