最少转向次数

题目描述

十六夜咲夜正准备为蕾米莉亚大小姐端上红茶。红魔馆的走廊可以看作一个 m 行 n 列的网格图。她只能向右或向下移动。

走廊的每个格点 (i,j) 可能放置了不同的物件：

0：空旷走廊，可以通行
1,2,3,4：家具、电源、孔洞、地线等障碍物，无法通行

咲夜需要从左上角的厨房 (0,0) 出发，到达右下角的大小姐房间 (m-1,n-1)。为了保证红茶不溢出，她希望在移动过程中尽可能减少转向的次数。所谓“转向”，是指移动方向从“向右”变为“向下”，或从“向下”变为“向右”。

数据范围： 0 < m, n ≤ 100，0 ≤ p_{i,j} ≤ 4

示例

输入：

输出： 2

说明：

走廊为 3×3 矩阵，其中 (0,1) 和 (2,0) 为障碍物。两条可行路径：

(0,0)→(1,0)→(1,1)→(1,2)→(2,2)：下→右（转向1）→右→下（转向2），共 2 次转向。
(0,0)→(1,0)→(1,1)→(2,1)→(2,2)：下→右（转向1）→下（转向2）→右（转向3），共 3 次转向。

最少转向次数为 2。

解题思路

方法一：DFS 回溯（暴力枚举所有路径）

使用 DFS 遍历所有合法路径，记录每条路径的坐标序列
对每条路径通过连续三个点检测转向：若 pre→mid 的方向与 mid→end 的方向不同，则计一次转向
取最小值

方法二：DP（推荐）

dp[i][j][0]：到达 (i,j) 且最后一步是向右走的最少转向次数
dp[i][j][1]：到达 (i,j) 且最后一步是向下走的最少转向次数

状态转移：

从左边 (i,j-1) 向右走到 (i,j)： dp[i][j][0] = min(dp[i][j-1][0], dp[i][j-1][1] + 1)
从上边 (i-1,j) 向下走到 (i,j)： dp[i][j][1] = min(dp[i-1][j][1], dp[i-1][j][0] + 1)

代码实现

function minTurnCount(grid) {
    const m = grid.length;
    const n = grid[0].length;

    if (m < 1 || n < 1) return -1;
    if (grid[0][0] !== 0 || grid[m - 1][n - 1] !== 0) return -1;
    if (m === 1 || n === 1) return 0;

    const INF = Infinity;
    const dp = Array.from({ length: m }, () =>
        Array.from({ length: n }, () => [INF, INF])
    );

    dp[0][0][0] = 0;
    dp[0][0][1] = 0;

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] !== 0) continue;
            if (i === 0 && j === 0) continue;

            // 从左边 (i, j-1) 向右走到 (i, j)
            if (j > 0 && grid[i][j - 1] === 0) {
                dp[i][j][0] = Math.min(
                    dp[i][j - 1][0],          // 之前也是向右，不转向
                    dp[i][j - 1][1] + 1       // 之前是向下，转向+1
                );
            }

            // 从上边 (i-1, j) 向下走到 (i, j)
            if (i > 0 && grid[i - 1][j] === 0) {
                dp[i][j][1] = Math.min(
                    dp[i - 1][j][1],          // 之前也是向下，不转向
                    dp[i - 1][j][0] + 1       // 之前是向右，转向+1
                );
            }
        }
    }

    const ans = Math.min(dp[m - 1][n - 1][0], dp[m - 1][n - 1][1]);
    return ans === INF ? -1 : ans;
}

复杂度分析

时间复杂度： O(m × n)，遍历整个网格一次。
空间复杂度： O(m × n)，dp 三维数组。可以优化为滚动数组 O(n)。

示例输入 / 输出

下面给出一组输入输出示例，便于对照题意与结果。

编号 min-turn-count难度中等

输入

输出