Problem B

//Problem B
/*
    BFS找路，判断楼梯状态，如果到达楼提前的步数是奇数
    那么便可快速通过楼梯，反之不能
    如果使用普通队列可能会出现步数大的结果，或者遍历所有情况再排查最小的情况
    优先队列则可以解决该问题，让步数小的排在前，减少麻烦
*/
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
int n,m,sx,sy;
char mp[30][30];
bool vis[30][30];
const int dp[4][2]={ {1,0},{-1,0},{0,1},{0,-1} };
struct Point {
    int x,y,step;
    bool operator <(const Point &z)const {
        return z.step<step;
    }
};
void DataIn() {
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            cin>>mp[i][j];
            if (mp[i][j]==‘S‘) sx=i, sy=j;
        }
    }
}
void DataOut() {
    priority_queue<Point> qu;
    Point a;
    a.x=sx, a.y=sy, a.step=0;
    qu.push(a);
    vis[a.x][a.y]=true;
    while (!qu.empty()) {
        Point head=qu.top();
        qu.pop();
        if (mp[head.x][head.y]==‘T‘) {
            printf("%d\n", head.step);
            return ;
        }
        for (int i=0; i<4; i++) {
            Point t=head;
            t.x+=dp[i][0];
            t.y+=dp[i][1];
            if(t.x<0 || t.x>=n || t.y<0 || t.y>=m || vis[t.x][t.y]==true || mp[t.x][t.y]==‘*‘) continue;                
            if (mp[t.x][t.y]==‘|‘) {
                if (head.step%2==0 && (i==0 || i==1)) {
                    t.x+=dp[i][0];
                    t.y+=dp[i][1];
                } else if (head.step%2==1 && (i==2 || i==3)) {
                    t.x+=dp[i][0];
                    t.y+=dp[i][1];
                } else {
                    t.x+=dp[i][0];
                    t.y+=dp[i][1];
                    vis[t.x][t.y]=true;
                    t.step=head.step+2;
                    qu.push(t);
                    continue;
                }
            } else if (mp[t.x][t.y]==‘-‘) {
                if (head.step%2==0 && (i==2 || i==3)) {
                    t.x+=dp[i][0];
                    t.y+=dp[i][1];
                } else if (head.step%2==1 && (i==0 || i==1)) {
                    t.x+=dp[i][0];
                    t.y+=dp[i][1];
                } else {
                    t.x+=dp[i][0];
                    t.y+=dp[i][1];
                      vis[t.x][t.y]=true;
                    t.step=head.step+2;
                    qu.push(t);
                    continue;
                }
            }
            t.step=head.step+1;
            vis[t.x][t.y]=true;
            qu.push(t);
        }
    }
    return ;
}
int main() {
    while (~scanf("%d %d", &n,&m)) {
        memset(vis, false, sizeof(vis)); 
        DataIn();
        DataOut();
    }
    return 0;
}