1.题意

给你一个有起点和终点的二维迷宫。你的任务是找出从起点到达终点的最快方法。最快的方法是走最少的步数，其中一步是向左、向右、向上或向下走。当然，你不能穿墙而过。

不过，也有一个问题：如果向同一方向迈出三步以上，就会失去平衡而摔倒。因此，禁止向同一方向连续走三步以上。向右走三步，然后向左走一步，再向右走三步是可以的。这与向右走五步的效果相同，但速度较慢。

2.分析

典型的dp问题，题目中提到不能连续一个方向走四步，所以转移方程需要考虑到方向和沿着当前方向已经走了几步，很容易得到dp数组的形式$$dp[N][N][4][4]$$，接着考虑转移的方式，一般求最短路的题目bfs和dfs均可，但在这道题中，由于bfs沿着步数的大小开始拓展，第一次遍历到终点既是最短路径，如果选择dfs，可能在某种状态第一次的遍历中没有得到最优答案，因此选用bfs

3.代码实现

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
const int N = 2e5 + 10;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
void solve() {
    int n,m;
    cin>>n>>m;
    int x,y;
    int nx;
    int ny;
    vector<vector<char>>a(n+1,vector<char>(m+1));
    vector<vector<vector<vector<int>>>>dp(n+1,vector<vector<vector<int>>>(m+1,vector<vector<int>>(4,vector<int>(4))));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            if(a[i][j]=='S') x=i,y=j;
            if(a[i][j]=='T') nx=i,ny=j;
        }
    }
    queue<array<int,4>>q;
    q.push({x,y,0,0});
    while(!q.empty()){
        auto [x,y,dir,step]=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            if(a[x+dx[i]][y+dy[i]]=='#') continue;
            if(i==dir){
                if(step==3||dp[x+dx[i]][y+dy[i]][i][step+1]) continue;
                q.push({x+dx[i],y+dy[i],dir,step+1});
                dp[x+dx[i]][y+dy[i]][i][step+1]=dp[x][y][i][step]+1;
                continue;
            }
            if(dp[x+dx[i]][y+dy[i]][i][1]) continue;
            q.push({x+dx[i],y+dy[i],i,1});
            dp[x+dx[i]][y+dy[i]][i][1]=dp[x][y][dir][step]+1;
        }
    }
    int ans=1e9;
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            if(dp[nx][ny][i][j]){
                ans=min(ans,dp[nx][ny][i][j]);
            }
        }
    }
    if(ans==1e9) ans=-1;
    cout<<ans<<endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T=1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}