第一篇题解

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

int n, m;

struct Node {
    int x, y;
    int pdir;  // 方向标记
    int step;  // 方向步数
};
queue<Node> q;
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};

int sx, sy, tx, ty;

int main() {
	
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    
	char mp[n + 10][m + 10] = {0};
    int vis[n + 10][m + 10][4][4] = {0}; 
    memset(vis, -1, sizeof vis);

    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            cin >> mp[i][j];
            if (mp[i][j] == 'S') {
                sx = i, sy = j;
                q.push({i, j, -1, 0});
            } 
        }
    }

    while (!q.empty()) {
        Node u = q.front();
        q.pop();

        for (int i = 0; i < 4; i ++) {
            int tx = u.x + dx[i];
            int ty = u.y + dy[i];
            
            if (tx < 1 || tx > n || ty < 1 || ty > m || mp[tx][ty] == '#') {
                continue;
            }

			// 将连续步数限制考虑是 "障碍" 
            int nstep;
            if (u.pdir == -1) {
                nstep = 1;
            } else {
                if (i == u.pdir) {
                    nstep = u.step + 1;
                    if (nstep > 3) continue; // 同方向，超过三步是不允许的
                } else {
                    nstep = 1; // 不同方向，标记从 1 开始 
                }
            }

            int ctot = (u.pdir == -1) ? 0 : vis[u.x][u.y][u.pdir][u.step];
            int ntot = ctot + 1;

            if (vis[tx][ty][i][nstep] == -1) {
                vis[tx][ty][i][nstep] = ntot;
                // 第一次到达即是最短
                if (mp[tx][ty] == 'T') {
                    cout << ntot << endl;
                    return 0;
                }
                q.push({tx, ty, i, nstep});
            }
        }
    }
    
    cout << -1 << endl;
    return 0;
}