题意理解

这是一个在网格上从起点 S 走到终点 T 的最短路径问题，但有限制：不能连续走同一个方向超过 3 步。

换句话说，如果你连续走了 $3$ 步向右，第 $4$ 步必须换方向（上下左右任意不同方向）。

关键点

• 普通 BFS 的状态只是 (x, y)，但这里不足以判断是否可以走下一步，因为还需要知道：上一步的方向是什么，以及 已经在这个方向上连续走了几步。
• 所以 BFS 的状态需要扩展为： [ (x, y, dir, steps) ] 其中：
  • dir：上一步移动的方向（0 上，1 右，2 下，3 左），用整数表示；起始点没有上一步，可以设成特殊值如 4。
  • steps：当前方向连续走了几步（1, 2, 3），如果 steps = 3 就不能再走相同方向。

状态空间大小

• 网格大小 $n \times m \le 2\times 10^5$。
• 方向：4 种 + 起点无方向 = 5 种。
• 连续步数：1,2,3 有效（因为走到 3 步后不能继续，但这是进入下一步时检查的）。 实际上可以设计 steps 为 已经连续走的步数，范围 0~3，其中 0 表示没有上一步（起点）。

所以状态数最多： [ \text{states} \le (n \times m) \times 5 \times 4 \approx 4\times 10^6 ] 这个范围 BFS 可以接受。

BFS 策略

1. 初始状态：(Sx, Sy, dir=4, steps=0)，步数 dist[Sx][Sy][4][0] = 0。
2. 从队列中取出状态 (x, y, d, s)，尝试向四个方向 nd 移动：
   • 如果 nd == d 且 s == 3，则跳过（不能再连续走相同方向）。
   • 如果 nd == d，则新方向的连续步数 ns = s + 1。
   • 如果 nd != d，则新方向的连续步数 ns = 1。
3. 如果新位置超出边界或碰到墙 #，则跳过。
4. 如果新状态未访问过，则入队，距离加 1。
5. 当到达 (Tx, Ty) 任意方向任意步数时，返回当前距离。

状态压缩

因为 $n, m$ 可能到 $10^4$，不能用 4 维数组 dist[n][m][5][4]，内存太大。

解决方案：

• 用 unordered_map 或 map 存储访问过的状态，但可能较慢。
• 更好的方法：因为 $n\times m \le 2\times 10^5$，我们用一维 ID 表示位置 id = x*m + y，然后用一个 4 维 vector 或 array 来存储，大小为： [ \text{size} = (n\times m) \times 5 \times 4 \le 4\times 10^6 ] 用 vector<int> dist(n*m*5*4, -1) 存储距离，内存约 $4\times 10^6 \times 4 \text{ bytes} = 16 \text{ MB}$，可接受。

索引计算： [ \text{index} = ((x*m + y) * 5 + dir) * 4 + steps ] 其中 dir 范围 0~4（4 表示无方向），steps 范围 0~3。

代码实现

#include <bits/stdc++.h>
using namespace std;

const int dx[4] = {-1, 0, 1, 0};  // 上右下左
const int dy[4] = {0, 1, 0, -1};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<string> grid(n);
    int sx = -1, sy = -1, tx = -1, ty = -1;

    for (int i = 0; i < n; i++) {
        cin >> grid[i];
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 'S') {
                sx = i; sy = j;
                grid[i][j] = '.';
            } else if (grid[i][j] == 'T') {
                tx = i; ty = j;
                grid[i][j] = '.';
            }
        }
    }

    // 状态 (x, y, dir, steps)
    // dir: 0~3 表示方向，4 表示无方向（起点）
    // steps: 0~3，已经连续走的步数，0 表示无前一步
    int totalCells = n * m;
    int totalStates = totalCells * 5 * 4;
    vector<int> dist(totalStates, -1);

    auto getIndex = [&](int x, int y, int dir, int steps) -> int {
        return ((x * m + y) * 5 + dir) * 4 + steps;
    };

    queue<tuple<int, int, int, int>> q;
    int startIdx = getIndex(sx, sy, 4, 0);
    dist[startIdx] = 0;
    q.emplace(sx, sy, 4, 0);

    while (!q.empty()) {
        auto [x, y, dir, steps] = q.front();
        q.pop();

        int curDist = dist[getIndex(x, y, dir, steps)];

        // 到达终点
        if (x == tx && y == ty) {
            cout << curDist << '\n';
            return 0;
        }

        for (int nd = 0; nd < 4; nd++) {
            int nx = x + dx[nd];
            int ny = y + dy[nd];

            // 越界或撞墙
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (grid[nx][ny] == '#') continue;

            int nsteps;
            if (nd == dir) {
                if (steps == 3) continue; // 不能连续走第4步同方向
                nsteps = steps + 1;
            } else {
                nsteps = 1;
            }

            int nidx = getIndex(nx, ny, nd, nsteps);
            if (dist[nidx] == -1) {
                dist[nidx] = curDist + 1;
                q.emplace(nx, ny, nd, nsteps);
            }
        }
    }

    // 无法到达
    cout << -1 << '\n';
    return 0;
}

复杂度分析

• 每个状态最多扩展 4 次，状态数 $O(n \times m \times 5 \times 4) \approx O(8 \times 10^5 \times 20)$？
  实际 $n \times m \le 2\times 10^5$，所以状态数 $\le 2\times 10^5 \times 20 = 4\times 10^6$。
• BFS 总操作数 $\le 4\times 10^6 \times 4 = 1.6\times 10^7$，可接受。
• 内存：dist 数组 $4\times 10^6$ 个整数，每个 4 字节 = 16 MB，加上队列开销，总体合理。

总结

这个 BFS 在普通 BFS 的基础上增加了两个维度：

• 上一步方向
• 当前方向连续步数

从而确保不违反“不能连续走同一方向超过 3 步”的规则。
状态总数可控，内存访问连续，可以高效运行。