原题大意

小Hi被坏女巫抓进里一间有N x M个格子组成的矩阵迷宫。

有些格子是小Hi可以经过的，我们用’.’表示；有些格子上有障碍物小Hi不能经过，我们用’#’表示。小Hi的起始位置用’S’表示，他需要到达用’T’表示的格子才能逃离迷宫。

麻烦的是小Hi被坏女巫施了魔法，他只能选择上下左右某一个方向，沿着这个方向一直走，直到遇到障碍物或者迷宫边界才能改变方向。新的方向可以是上下左右四个方向之一。之后他还是只能沿着新的方向一直走直到再次遇到障碍物或者迷宫边界……

小Hi想知道他最少改变几次方向才能逃离这个迷宫。

算法分析

bfs，起初想用dfs，发现如果终点不在边界就不好判断了，所以改用bfs，但是由于考虑不周导致被卡了两天，这种题还是要细心一点。

程序代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;
char g[maxn][maxn];
int vis[maxn][maxn];
int n, m;
int sx, sy, ex, ey;
int d[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
struct point{
    int x, y, pre, step;
};
int check(int x, int y){
    if(x < 0 || y < 0 || x >= n || y >= m || g[x][y] == '#') return false;
    return true;
}
int p_dir(int now_dir){
    if(now_dir == 0) return 1;
    if(now_dir == 1) return 0;
    if(now_dir == 2) return 3;
    if(now_dir == 3) return 2;
    if(now_dir == -1) return 5;
}
int move(int &x, int &y, int i){
        if(g[x][y] == 'T') return 1;//！！！可能一开始就是T！！！
    while(check(x+d[i][0],y+d[i][1])){
        x+=d[i][0];
        y+=d[i][1];
        if(g[x][y] == 'T') return 1;
    }
    return 0;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> g[i][j];
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
        {
            if(g[i][j] == 'S') sx = i, sy = j;
            if(g[i][j] == 'T') ex = i, ey = j;
        }
    point st = {sx, sy, -1, 0};//初始时令起点方向为-1
    queue<point> q;
    q.push(st);
    int fg = 0;
    memset(vis, 0 ,sizeof(vis));
    vis[sx][sy] = 1;
    while(!q.empty()){
        point now = q.front();
        q.pop();
        int nowx = now.x;
        int nowy = now.y;
        if(now.pre != -1)
        {
            if(vis[nowx][nowy] == 1) continue;
            vis[nowx][nowy] = 1;
        }

        for(int i = 0; i < 4; i++){
            if(p_dir(now.pre) == i || now.pre == i) continue;//不重复走
            int nx = nowx,ny = nowy;
            fg = move(nx,ny,i);

            if(fg == 1) {
                cout << now.step<<endl;
                break;
            }
            if(!(nowx == nx && nowy == ny))
            {
                point t = {nx, ny, i, now.step+1};
                q.push(t);
            }
        }
        if(fg == 1) break;
    }
    if(fg == 0)cout << "-1"<<endl;
    return 0;
}