题意
给出一个三维迷宫,上下左右前后六联通的走法,给你起点和终点,要你求从起点到终点的最少步数。
思路
拿到问题,首先发现是在一个迷宫里面进行,联通方向有六个,求最短路,且数据规模较小,这些都是适用于BFS解题的特征。接下来的关键就是正确地实现BFS了,对BFS的实作原理不太理解的话,不妨先思考在一棵树上遍历时的BFS的实作过程。在BFS的实现过程中,需要正确地判断某个点是不是有效,需要在正确的时机打访问标记,需要正确地操作队列,注意这三点一般不会产生问题。本题并不需要我们实现图结构,因为迷宫本身就已经可以看成图了。在BFS过程中,因为搜索完当前深度的全部状态,才会取出更大深度的状态,所以在BFS过程中,只要我们进入了表示走到终点的状态,就无需再考虑其他状态了,因为即使其他状态也能表示到达终点,其深度(步数)也一定不会比第一个到达的状态少,这样可以节省一些时间。还有一些诸如“连通向量”等小技巧,可以减轻编码负担。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> using namespace std; char grid[32][32][32];//z,y,x int L,R,C;//maxz maxy maxx int dir[6][3] = {{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}}; struct Point { int z,y,x,step; Point(int _z,int _y,int _x,int _step){ z = _z; y = _y; x = _x; step = _step; } Point(){ } }; bool isValid(int z,int y,int x){ if (z < 1 || z > L) { return false; } if (y < 1 || y > R) { return false; } if (x < 1 || x > C) { return false; } if (grid[z][y][x] == '#') { return false; } return true; } bool vis[32][32][32]; int bfs(Point init){ queue<Point> que; que.push(init); memset(vis, false, sizeof(vis)); while (!que.empty()) { Point now = que.front(); que.pop(); if (vis[now.z][now.y][now.x]) { continue; } vis[now.z][now.y][now.x] = true; if (grid[now.z][now.y][now.x] == 'E') { return now.step; } for (int i = 0; i < 6; i++) { int newz = now.z + dir[i][0]; int newy = now.y + dir[i][1]; int newx = now.x + dir[i][2]; if (!vis[newz][newy][newx] && isValid(newz, newy, newx)) { que.push(Point(newz,newy,newx,now.step+1)); } } } return -1; } int main(){ while (scanf(" %d %d %d",&L,&R,&C)) { if (L == 0 && R == 0 && C == 0) { break; } Point init; for (int i = 1; i <= L; i++) { for (int j = 1; j <= R; j++) { for (int k = 1; k <= C; k++) { scanf(" %c",&grid[i][j][k]); if (grid[i][j][k] == 'S') { init = Point(i,j,k,0); } } } } int res = bfs(init); if (res == -1) { cout << "Trapped!" << endl; }else{ cout << "Escaped in " << res << " minute(s)." << endl; } } return 0; } |
September 10, 2015
[…] POJ 2251 Dungeon Master […]