题目

Problem 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

7

##　Hint

地图如下

题解

猛一看，这道题思路非常清晰，二维矩阵中进行BFS，根据时间来判断梯子的走向。
然而交了好多次都没AC
开始是由于直接复制BFS的模板，结果忘记改maxn导致超时（竟然不是RE）
后来就是莫名其妙的WA
再看一遍题，可以发现一个很关键的地方
题目中没有说如果路径不存在则输出-1
也就是说，不管怎么样一定存在路径

那么我们仔细想下，类似

S|T

这样的迷宫显然是没有路径的，如果通过绕路的方式，可以发现在回到该位置后，梯子的方向不变。
那么，真相只有一个：可以原地等待一步

明白了这点，稍加修改就可以得到符合题意得算法

另外有一点需要注意：
由于等待改变了BFS层数的先后顺序(等待的层数额外加1)，这回破坏BFS天然的顺序
因此，要采用优先队列来存储

代码

/*
By:OhYee
Github:OhYee
Email:oyohyee@oyohyee.com
Blog:http://www.cnblogs.com/ohyee/

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
using namespace std;

//DEBUG MODE
#define debug 0

//循环
#define REP(n) for(int o=0;o<n;o++)

const int maxn = 30;
int n,m;
char Map[maxn][maxn];

#if debug
pair<int,int> last[maxn][maxn];
#endif

const int delta[4] = {1,-1,0,0};

struct point {
    int x,y;
    int dis;//楼梯是否已变化
    point(int a,int b,int c) {
        x = a;
        y = b;
        dis = c;
    }
    bool operator < (const point &rhs) const {
        return dis>rhs.dis;
    }
};

int BFS(int s1,int s2,int v1,int v2) {
    priority_queue<point> Q;
    int dis[maxn][maxn];
    memset(dis,-1,sizeof(dis));

    Q.push(point(s1,s2,false));
    dis[s1][s2] = 0;

    while (!Q.empty()) {
        point temp = Q.top();
        Q.pop();

        int x = temp.x;
        int y = temp.y;
        int dist = temp.dis;

        REP(4) {
            int xx = x + delta[o];
            int yy = y + delta[3 - o];
            int dd = dist + 1;

            if (xx < 0 || xx >= m || yy < 0 || yy >= n || Map[xx][yy] == '*')
                continue;
            if (Map[xx][yy] == '-' || Map[xx][yy] == '|') {//是梯子
                if (x == xx) {//水平方向移动
                    //需要等待一步
                    if ((Map[xx][yy] == '-' && dist % 2 == 1) || (Map[xx][yy] == '|' && dist % 2 != 1))
                        dd++;
                    yy += yy - y;
                } else {//竖直方向移动
                    //需要等待一步
                    if ((Map[xx][yy] == '|' && dist % 2 == 1) || (Map[xx][yy] == '-' && dist % 2 != 1))
                        dd++;
                    xx += xx - x;
                }
            }
            if (xx < 0 || xx >= m || yy < 0 || yy >= n || Map[xx][yy] != '.')
                continue;

            if (dis[xx][yy] == -1) {
                dis[xx][yy] = dd;
#if debug
                last[xx][yy] = pair<int,int>(x,y);
#endif
                if (xx == v1 && yy == v2)
                    break;
                Q.push(point(xx,yy,dd));

            }
        }
    }

#if debug
    pair<int,int> w;
    w = pair<int,int>(v1,v2);
    while (!(w.first == s1 && w.second == s2)) {
        printf("%d %d\n",w.first,w.second);
        w = last[w.first][w.second];
    }
#endif

    return dis[v1][v2];
}

bool Do() {
    int s1,v1;
    int s2,v2;
    if (scanf("%d%d\n",&m,&n) == EOF)
        return false;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++) {
            scanf("\n%c\n",&Map[i][j]);
            if (Map[i][j] == 'S') {
                s1 = i;
                s2 = j;
                Map[i][j] = '.';
            }
            if (Map[i][j] == 'T') {
                v1 = i;
                v2 = j;
                Map[i][j] = '.';
            }
        }

#if debug
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++)
            printf("%c",Map[i][j]);
        printf("\n");
    }
#endif

    printf("%d\n",BFS(s1,s2,v1,v2));
    return true;
}


int main() {
    while (Do());
    return 0;
}

HDU 1180.诡异的楼梯