Description
Hogwarts正式开学以后,Harry发现在Hogwarts里,某些楼梯并不是静止不动的，相反,他们每隔一分钟就变动一次方向.
比如下面的例子里,一开始楼梯在竖直方向,一分钟以后它移动到了水平方向,再过一分钟它又回到了竖直方向.Harry发现对他来说很难找到能使得他最快到达目的地的路线,这时Ron(Harry最好的朋友)告诉Harry正好有一个魔法道具可以帮助他寻找这样的路线,而那个魔法道具上的咒语,正是由你纂写的.Input
测试数据有多组，每组的表述如下：
第一行有两个数,M和N,接下来是一个M行N列的地图,'*'表示障碍物,'.'表示走廊,'|'或者'-'表示一个楼梯,并且标明了它在一开始时所处的位置:'|'表示的楼梯在最开始是竖直方向,'-'表示的楼梯在一开始是水平方向.地图中还有一个'S'是起点,'T'是目标,0<=M,N<=20,地图中不会出现两个相连的梯子.Harry每秒只能停留在'.'或'S'和'T'所标记的格子内.Output
只有一行,包含一个数T,表示到达目标的最短时间.
注意:Harry只能每次走到相邻的格子而不能斜走,每移动一次恰好为一分钟,并且Harry登上楼梯并经过楼梯到达对面的整个过程只需要一分钟,Harry从来不在楼梯上停留.并且每次楼梯都恰好在Harry移动完毕以后才改变方向.Sample Input
5 5 **..T **.*. ..|.. .*.*. S....Sample Output
7Hint
Hint 地图如下：
猛一看，这道题思路非常清晰，二维矩阵中进行BFS，根据时间来判断梯子的走向。
然而交了好多次都没AC
开始是由于直接复制BFS的模板，结果忘记改maxn导致超时（竟然不是RE）
后来就是莫名其妙的WA
再看一遍题，可以发现一个很关键的地方
题目中没有说如果路径不存在则输出-1
也就是说，不管怎么样一定存在路径
那么我们仔细想下，类似
S|T
这样的迷宫显然是没有路径的，如果通过绕路的方式，可以发现在回到该位置后，梯子的方向不变。
那么，真相只有一个：可以原地等待一步
明白了这点，稍加修改就可以得到符合题意得算法
另外有一点需要注意：
由于等待改变了BFS层数的先后顺序(等待的层数额外加1)，这回破坏BFS天然的顺序
因此，要采用优先队列来存储
1 /* 2 By:OhYee 3 Github:OhYee 4 Email:oyohyee@oyohyee.com 5 Blog:http://www.cnblogs.com/ohyee/ 6 7 かしこいかわいい？ 8 エリーチカ！ 9 要写出来Хорошо的代码哦~ 10 */ 11 #include <cstdio> 12 #include <algorithm> 13 #include <cstring> 14 #include <cmath> 15 #include <string> 16 #include <iostream> 17 #include <vector> 18 #include <list> 19 #include <queue> 20 #include <stack> 21 using namespace std; 22 23 //DEBUG MODE 24 #define debug 0 25 26 //循环 27 #define REP(n) for(int o=0;o<n;o++) 28 29 const int maxn = 30; 30 int n,m; 31 char Map[maxn][maxn]; 32 33 #if debug 34 pair<int,int> last[maxn][maxn]; 35 #endif 36 37 const int delta[4] = {1,-1,0,0}; 38 39 struct point { 40 int x,y; 41 int dis;//楼梯是否已变化 42 point(int a,int b,int c) { 43 x = a; 44 y = b; 45 dis = c; 46 } 47 bool operator < (const point &rhs) const { 48 return dis>rhs.dis; 49 } 50 }; 51 52 int BFS(int s1,int s2,int v1,int v2) { 53 priority_queue<point> Q; 54 int dis[maxn][maxn]; 55 memset(dis,-1,sizeof(dis)); 56 57 Q.push(point(s1,s2,false)); 58 dis[s1][s2] = 0; 59 60 while (!Q.empty()) { 61 point temp = Q.top(); 62 Q.pop(); 63 64 int x = temp.x; 65 int y = temp.y; 66 int dist = temp.dis; 67 68 REP(4) { 69 int xx = x + delta[o]; 70 int yy = y + delta[3 - o]; 71 int dd = dist + 1; 72 73 if (xx < 0 || xx >= m || yy < 0 || yy >= n || Map[xx][yy] == '*') 74 continue; 75 if (Map[xx][yy] == '-' || Map[xx][yy] == '|') {//是梯子 76 if (x == xx) {//水平方向移动 77 //需要等待一步 78 if ((Map[xx][yy] == '-' && dist % 2 == 1) || (Map[xx][yy] == '|' && dist % 2 != 1)) 79 dd++; 80 yy += yy - y; 81 } else {//竖直方向移动 82 //需要等待一步 83 if ((Map[xx][yy] == '|' && dist % 2 == 1) || (Map[xx][yy] == '-' && dist % 2 != 1)) 84 dd++; 85 xx += xx - x; 86 } 87 } 88 if (xx < 0 || xx >= m || yy < 0 || yy >= n || Map[xx][yy] != '.') 89 continue; 90 91 if (dis[xx][yy] == -1) { 92 dis[xx][yy] = dd; 93 #if debug 94 last[xx][yy] = pair<int,int>(x,y); 95 #endif 96 if (xx == v1 && yy == v2) 97 break; 98 Q.push(point(xx,yy,dd)); 99 100 } 101 } 102 } 103 104 #if debug 105 pair<int,int> w; 106 w = pair<int,int>(v1,v2); 107 while (!(w.first == s1 && w.second == s2)) { 108 printf("%d %d ",w.first,w.second); 109 w = last[w.first][w.second]; 110 } 111 #endif 112 113 return dis[v1][v2]; 114 } 115 116 bool Do() { 117 int s1,v1; 118 int s2,v2; 119 if (scanf("%d%d ",&m,&n) == EOF) 120 return false; 121 for (int i = 0; i < m; i++) 122 for (int j = 0; j < n; j++) { 123 scanf(" %c ",&Map[i][j]); 124 if (Map[i][j] == 'S') { 125 s1 = i; 126 s2 = j; 127 Map[i][j] = '.'; 128 } 129 if (Map[i][j] == 'T') { 130 v1 = i; 131 v2 = j; 132 Map[i][j] = '.'; 133 } 134 } 135 136 #if debug 137 for (int i = 0; i < m; i++) { 138 for (int j = 0; j < n; j++) 139 printf("%c",Map[i][j]); 140 printf(" "); 141 } 142 #endif 143 144 printf("%d ",BFS(s1,s2,v1,v2)); 145 return true; 146 } 147 148 149 int main() { 150 while (Do()); 151 return 0; 152 }