题意
对于一个入口和出口都在边界的迷宫,有两种一定能保证走出迷宫的方案,想象你自己站在迷宫的入口,你可以一直让左手扶着墙,贴着墙走,这样最后一定会走到终点。你也可以一直让右手扶着墙,贴着墙走,最终也一定会到达终点。现在要你模拟这两种策略,分别输出这样走要经历的步数,同时再算出不限于上述策略的走出迷宫的最短路方案。
思路
对于最短路,只要使用常规的BFS就可以解决。难点在于如何模拟左手扶墙和右手扶墙。如果是以左手扶墙来遍历迷宫的话,其实是相当于每一次都先尝试去走当前面朝方向的左边,若无法走,尝试直行,还不行的话,再尝试右行和上行。每一次行走,你要想想自己身处迷宫之中,并且根据你的行走动作来改变自己的朝向,模拟这个过程就是本题的难点。
有一种比较聪明的实现方式,就是把原来的行进向量(dir),也当成朝向向量来用,往左行走相当于朝向向量左转,直行相当于无旋转,右行相当于向右旋转,下行相当于两次右旋。每一次前进时把旋转完的朝向向量当行进向量用就可以了,下一次还是按照上面所述的循环操作。
本题还有一个技巧,你只需要实现扶一边墙行走,因为从起点扶一边墙走到终点相当于从终点扶另一边墙走到起点,所以你在第一次行走完之后,只要交换起点终点的’S’和’E’,然后再执行一次从”原终点”到”原起点”的行走,就可以了。
代码
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 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 |
#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[42][42]; void counterClockwiseRotate(int &y,int &x){ int t = -y; y = x; x = t; } void clockwiseRotate(int &y,int &x){ int t = -x; x = y; y = t; } int follow(int inity,int initx){ int cury = inity,curx = initx,step = 1; int diry = 0,dirx = -1; while (grid[cury][curx] != 'E') { for (int i = 0; i < 4; i++) { int nxty = cury + diry; int nxtx = curx + dirx; if (grid[nxty][nxtx] && grid[nxty][nxtx] != '#') { cury = nxty; curx = nxtx; step++; counterClockwiseRotate(diry, dirx); break; } clockwiseRotate(diry, dirx); } } return step; } struct State{ int y,x,step; State(int _y,int _x,int _step){ y = _y; x = _x; step = _step; } State(){ } }; bool vis[42][42]; int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}; int bfs(int inity, int initx){ queue<State> que; que.push(State(inity, initx,1)); memset(vis, false, sizeof(vis)); while (!que.empty()) { State now = que.front(); que.pop(); int nowy = now.y; int nowx = now.x; if (vis[nowy][nowx]) { continue; } vis[nowy][nowx] = true; if (grid[nowy][nowx] == 'E') { return now.step; } for (int i = 0; i < 4; i++) { int nxty = nowy + dir[i][0]; int nxtx = nowx + dir[i][1]; if (grid[nxty][nxtx] && !vis[nxty][nxtx] && grid[nxty][nxtx] != '#') { que.push(State(nxty, nxtx,now.step+1)); } } } return -1; } int main(){ int caseCnt; scanf(" %d",&caseCnt); while (caseCnt--) { int m,n; memset(grid, 0, sizeof(grid)); scanf(" %d %d",&m,&n); int inity=0,initx=0,endy=0,endx=0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { scanf(" %c",&grid[i][j]); if(grid[i][j] == 'S'){ inity = i; initx = j; } if(grid[i][j] == 'E'){ endy = i; endx = j; } } } swap(grid[inity][initx], grid[endy][endx]); printf("%d ",follow(endy, endx)); swap(grid[inity][initx], grid[endy][endx]); printf("%d %d\n",follow(inity, initx),bfs(inity, initx)); } return 0; } |
September 11, 2015
[…] POJ 3083 Children of the Candy Corn […]