LeetCode 980. 不同路径 III

2022-08-31 HGNULB 约 11 分钟

文章信息 8 个分类 5 个标签

分类

题目描述

✅ 980. 不同路径 III

题意分析

题目要的是一个精确的计数：从唯一的起点格出发，走到唯一的终点格，途中每一个可以踏足的格子都恰好踩一次，问这样的走法一共有多少种。

「恰好一次」是两条要求叠在一起：一个格子不能重复踩，同时也不能被漏掉。只满足前者的走法很多，能同时满足后者的往往寥寥无几。

约束里最关键的信号是网格总格数不超过 20，行列各自不超过 20 但乘积被压得很小。这个量级明确告诉我们，答案不需要靠什么闭式公式或者逐格递推得到，允许把每一种走法真的走出来。

边界上要留意三点：值为 -1 的障碍格既不能踏足，也不算在「必须走完」的集合里；起点格和终点格自身也属于必须被踩到的格子，不能当成免费的出入口；网格里保证恰好有一个起点和一个终点，所以不必处理多起点或无起点的退化情况。

解法：原地标记的回溯搜索

核心思路

最直接的暴力是把所有非障碍格子排成一个序列，枚举全部排列，再检查这个排列是不是首格为起点、尾格为终点、且相邻两格在网格上确实相邻。这样做逻辑上无懈可击，但 20 个格子的全排列量级完全不可接受，而且绝大多数排列在第二个格子处就已经不合法了。

瓶颈正在于此：暴力把「合法性检查」全部推迟到排列生成完毕之后，前缀早就废掉了却还在往下枚举。反过来想，路径本身是一格一格长出来的，每往前走一步就能立刻判断这一步是否越界、是否撞上障碍、是否踩了已经踩过的格子，不合法就当场掐断。

再观察一步：既然路径不允许重复踩格子，那么「已经踩过的格子集合」的大小完全由当前路径长度决定。也就是说，我们并不需要真的持有那个集合来做判断，只需要一个计数器就能知道还剩多少格子没踩。而「不能踩重复」这件事，用把当前格子临时改写成障碍值 -1 的办法就地表达，回溯时改回去即可，连额外的访问数组都省了。

于是得到贯穿整个递归的不变量：每次调用 dfs(r, c, remain) 时，格子 $(r, c)$ 是即将被踩、但尚未被标记的合法格子，而 remain 恰好等于「把 $(r, c)$ 自己算在内、当前仍未被踩过的非障碍格子总数」。初次调用时路径为空，未踩过的就是全部非障碍格子，所以 remain 初值取 total；每往前走一格，已踩数加一，未踩数减一，所以递归时传 remain - 1，不变量自动维持。

这条不变量直接给出了计数时机。走到终点格时，如果此刻 remain == 1，说明除了终点自己以外再没有未踩的格子，这条路径踩满了全部格子，是一个合法答案；如果 remain > 1，说明还有格子被落下了，这只是一次提前撞上终点的失败尝试，必须丢弃而不能计数。

解题步骤

先整体扫描一遍网格，统计所有值不等于 -1 的格子数量得到 total，同时记下值为 1 的起点坐标。为什么要先扫一遍：remain 的语义依赖于「非障碍格子总数」这个全局量，不先算出来就无法在递归里判断路径是否踩满。

从起点调用 dfs(startRow, startCol, total)。为什么初值是 total 而不是 total - 1：不变量规定 remain 包含当前格子自己，进入递归时起点还没被标记，所以未踩数就是全部。

进入递归后第一件事是判断当前格是否为终点（值为 2）。若是，仅当 remain == 1 才把答案加一，随后无条件返回。为什么终点要立刻返回：题目要求终点是路径的最后一格，从终点继续往外走出去的走法不是合法路径。

不是终点，就把当前格子的值临时改成 -1。为什么用 -1 而不是另建 visited 数组：邻格合法性判断本来就要排除 -1，把「已踩」和「障碍」统一成同一个值，四方向枚举里只需要一次比较。

枚举上下左右四个方向，先做越界检查再读取邻格的值，跳过越界和值为 -1 的邻格，其余邻格以 remain - 1 递归。为什么必须先判越界再读值：顺序反了会先访问数组再检查下标，直接越界崩溃。

四个方向都试完之后，把当前格子的值恢复成进入时保存的原值。为什么要恢复：当前格子只是这一条路径上的已踩格，兄弟分支里它可能是完全自由的，不恢复就会污染后续搜索。

全部搜索结束后返回累计的答案。

以 grid = [[1,0,0],[0,0,2]] 走一遍：扫描得到没有障碍格，total = 6，起点在 $(0,0)$，终点在 $(1,2)$。方向枚举顺序取「下、上、右、左」。

调用 dfs(0,0,6)：不是终点，把 $(0,0)$ 标为 -1。向下得到 $(1,0)$ 合法，进入 dfs(1,0,5)。

dfs(1,0,5)：不是终点，标 -1。向下越界，向上是 $(0,0)$ 已被标 -1 跳过，向右得到 $(1,1)$，进入 dfs(1,1,4)。

dfs(1,1,4)：不是终点，标 -1。向上得到 $(0,1)$，进入 dfs(0,1,3)；这一支返回后再向右撞到终点 $(1,2)$，此时 remain 传下去是 3，3 != 1，不计数直接返回；向左是已标记的 $(1,0)$，跳过。

dfs(0,1,3)：不是终点，标 -1。向下是已标记的 $(1,1)$ 跳过，向右得到 $(0,2)$，进入 dfs(0,2,2)。

dfs(0,2,2)：不是终点，标 -1。向下撞到终点，进入 dfs(1,2,1)，remain == 1 成立，答案累加为 1。这条路径正是 $(0,0) \to (1,0) \to (1,1) \to (0,1) \to (0,2) \to (1,2)$，六格全踩满。随后 $(0,2)$、$(0,1)$、$(1,1)$、$(1,0)$ 依次恢复原值 0。

回到 dfs(0,0,6) 的第二个方向，向右进入 dfs(0,1,5)：向下走 $(1,1)$ 再向左走 $(1,0)$ 时，$(1,0)$ 的上邻和右邻都已被标记，走进死胡同原路返回；dfs(1,1,4) 向右撞终点时 remain 为 3，不计数；dfs(0,2,4) 向下撞终点时 remain 同样为 3，也不计数。

所有分支耗尽，最终答案为 1。注意终点其实被撞到过四次，但只有 remain == 1 的那一次是有效路径，这正是不变量在起作用。

代码实现

class Solution {
    // 先统计所有非障碍格子的数量，DFS 时用 remain 表示当前格子在内还剩多少格子必须走完。
    private int rows;
    private int cols;
    private int result;

    public int uniquePathsIII(int[][] grid) {
        rows = grid.length;
        cols = grid[0].length;

        int startRow = 0;
        int startCol = 0;
        int total = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] != -1) {
                    total++;
                }
                if (grid[i][j] == 1) {
                    startRow = i;
                    startCol = j;
                }
            }
        }

        dfs(grid, startRow, startCol, total);
        return result;
    }

    private void dfs(int[][] grid, int row, int col, int remain) {
        if (grid[row][col] == 2) {
            if (remain == 1) {
                result++;
            }
            return;
        }

        int original = grid[row][col];
        grid[row][col] = -1;

        int[] dr = {1, -1, 0, 0};
        int[] dc = {0, 0, 1, -1};

        for (int k = 0; k < 4; k++) {
            int nr = row + dr[k];
            int nc = col + dc[k];
            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) {
                continue;
            }
            if (grid[nr][nc] == -1) {
                continue;
            }
            dfs(grid, nr, nc, remain - 1);
        }

        grid[row][col] = original;
    }
}

func uniquePathsIII(grid [][]int) int {
    // 先统计所有非障碍格子的数量，DFS 时用 remain 表示当前格子在内还剩多少格子必须走完。
    rows := len(grid)
    cols := len(grid[0])

    total := 0
    startRow, startCol := 0, 0
    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if grid[i][j] != -1 {
                total++
            }
            if grid[i][j] == 1 {
                startRow, startCol = i, j
            }
        }
    }

    result := 0
    dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}

    var dfs func(r, c, remain int)
    dfs = func(r, c, remain int) {
        if grid[r][c] == 2 {
            if remain == 1 {
                result++
            }
            return
        }

        original := grid[r][c]
        grid[r][c] = -1

        for _, d := range dirs {
            nr := r + d[0]
            nc := c + d[1]
            if nr < 0 || nr >= rows || nc < 0 || nc >= cols {
                continue
            }
            if grid[nr][nc] == -1 {
                continue
            }
            dfs(nr, nc, remain-1)
        }

        grid[r][c] = original
    }

    dfs(startRow, startCol, total)
    return result
}

复杂度分析

时间复杂度：$O(3^{mn})$，路径长度上限是格子总数 $mn$，除起点外每一步都不可能折返回上一格（上一格已被标成 -1），所以每层最多分裂出三个分支，搜索树规模是 $3$ 的路径长度次方；题目把 $mn$ 压到 20 以内，正是为了让这个指数量级可以承受。

空间复杂度：$O(mn)$，原地标记不额外占用空间，开销全部来自递归栈，而路径不重复踩格子，栈深最多等于格子总数。

关键点总结

计数类的排列搜索，不要先生成完整候选再验证，要把可行性判断下沉到每一步扩展上，让非法前缀在最早的位置被砍断。

定义搜索参数时要写出一句可以逐层验证的不变量，这里是「remain 等于含当前格在内的未访问非障碍格数」，有了它，终止条件 remain == 1 是推导出来的而不是猜出来的。

当「已访问」和「不可访问」在判断逻辑上完全等价时，可以把访问标记合并进原数组，用一个哨兵值同时承担两种含义，省掉辅助结构也减少了两处判断。

回溯的对称性要成对写：改状态和恢复状态必须在同一个函数体里一眼可见，中途的 return 是最容易漏掉恢复的地方。

面试视角：这题的考点不是会不会写 DFS，而是能否说清「为什么到了终点还不能计数」。面试官通常会顺势追问剪枝，可以主动提连通性剪枝（若剩余空白格被分割成不连通的多块则直接返回）和死角剪枝，展示对搜索树规模的敏感度。

面试视角：另一个高频追问是「为什么不用动态规划」。答案是路径计数 DP 的状态只记录位置，无法表达「哪些格子已被踩过」这个集合约束；如果非要 DP，就得把访问集合压进状态位，退化成状压 DP，格子数上限 20 恰好也支持这条路线。

易错点总结

错误写法：走到终点就无条件 result++，不检查 remain == 1。用例 grid = [[1,0,0],[0,0,2]] → 搜索过程中终点被撞到四次，答案从正确的 1 膨胀成 4，这类「提前抵达终点」的半截路径全被误计。

错误写法：统计 total 时把障碍格也算进去。用例任意含 -1 的网格 → remain 的基数被抬高，路径踩满全部空白格时 remain 停在障碍格数加一而非 1，判定永不成立，答案恒为 0。

错误写法：统计 total 时只数值为 0 的空白格，漏掉起点和终点。用例 grid = [[1,0,0],[0,0,2]] → total 变成 4，那条六格全踩的合法路径抵达终点时 remain 已经是 -1，答案错成 0。

错误写法：递归时传 remain 而不是 remain - 1。用例 grid = [[1,0,0],[0,0,2]] → remain 全程恒等于 6，remain == 1 永远不成立，答案恒为 0。

错误写法：邻格合法性只允许值为 0 的格子递归，即写成 if (grid[nr][nc] != 0) continue;。用例任意网格 → 终点的值是 2，永远进不去递归，答案恒为 0。

错误写法：先读取 grid[nr][nc] 判断是否为 -1，再检查下标是否越界。用例起点位于网格角落的任意输入 → 越界下标直接抛出数组越界异常。

错误写法：把当前格标记为 -1 之后才判断是否为终点，并在计数分支里直接 return，没有恢复终点格。用例 grid = [[1,0,0],[0,0,2]] → 终点被永久改成 -1，后续所有分支都跳过它，答案严重偏小。

错误写法：四个方向递归完毕后忘记把当前格恢复原值。用例任意存在多条路径的网格 → 第一条路径踩过的格子在整棵搜索树里一直保持 -1，兄弟分支被大面积错误封死，答案偏小。

相似题目

题目	难度	考察点
79. 单词搜索	中等	沿目标串逐字符匹配，找到一条即可提前返回
212. 单词搜索 II	困难	多模式串共享字典树，靠前缀失配整片剪枝
1219. 黄金矿工	中等	路径长度自由，目标是权值最大而非方案计数
剑指 Offer 12. 矩阵中的路径	中等	起点不固定，需枚举每个格子做存在性判定