LeetCode 980. 不同路径 III

约 7 分钟
文章信息 8 个分类 4 个标签
分类
LeetCode CodeTop 困难 未解决 2-5 华为 微软 携程
标签
数组 矩阵 位运算 回溯

题目描述

✅ 980. 不同路径 III

image-20260928225436165

image-20260928225436166

题意分析

网格中 1 是唯一起点，2 是唯一终点，0 是可行走空格，-1 是障碍。每次只能向上下左右相邻格移动，统计从起点出发、在终点结束，并且恰好经过每个非障碍格一次的路径数量。

起点和终点也属于必须访问的格子。不能重复走某格，也不能提前到达终点后再离开补走其他格子。网格总格数不超过二十，可以通过回溯枚举路径；只求普通的起终点连通路径并不足以满足要求。

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

核心思路

[!blue]

先统计所有非障碍格数量，并找到起点。递归参数 remain 表示这条候选路径上尚未访问的格子数，包含当前刚进入、还未标记的格子。第一次从起点进入时，它等于全部可走格数。

如果当前是终点，只有 remain == 1 才能计入答案：此时唯一尚未处理的格子就是终点，其他可走格都已访问。无论是否计数，都立即结束当前分支，因为路径到终点就必须停止。

对非终点，保存该格原值，再临时改成 -1，让它在本条路径后续搜索中与障碍一样不可进入。枚举四个相邻位置，排除越界、障碍和已经访问的格子，然后以 remain - 1 递归。减一表示当前格已经走过，下一次调用的剩余数仍包含下一格。

搜索完所有后续方向后，把当前格恢复为原值，使其他候选路径可以重新使用它。标记限制的是一条路径，不能变成整个搜索期间的永久访问记录；恢复原值还保证起点标记不会被误改成普通空格。

每一步枚举全部合法相邻格，完整覆盖可能的走法；路径标记保证没有重复访问，终点处的剩余计数保证没有漏掉格子。三个条件共同成立才是一条答案，单靠当前位置或剩余数量都无法代替访问状态。

解题步骤

  1. 扫描网格，统计非障碍格总数，并记录起点位置。
  2. 从起点调用 DFS，初始剩余数量为总数。
  3. 到终点时，仅在 remain == 1 时增加答案，然后直接返回。
  4. 其他位置先保存原值并标记为不可用，向合法四邻递归，传入 remain - 1。
  5. 所有方向返回后恢复原值；完整搜索结束后返回路径数。

代码实现

class Solution {
    private int rows;
    private int cols;
    private int result;

    public int uniquePathsIII(int[][] grid) {
        // 每次调用重置路径数，网格恢复后可再次独立计算。
        result = 0;
        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 {
    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(mn + 3^K)$ 上界，其中 m、n 为行列数，K 为可走格数。预处理扫描网格；搜索第一步至多四个方向，之后至少不能立即走回前一格，每层至多三种继续选择。
  • 空间复杂度：$O(K)$，一条路径最多包含 K 个格子，空间主要来自递归栈；访问标记复用输入网格并在返回时恢复。

关键点总结

[!green]

  • remain 包含当前格，所以抵达终点时检查一，而不是零。
  • 路径标记防止重复，剩余计数检验完整覆盖，两者缺一不可。
  • 标记和恢复围绕每个递归调用成对出现，保证分支之间互不污染。

易错点总结

[!yellow]

  • 一到终点就计数，会把尚未经过全部可走格子的普通路径也算入。
  • 到终点后继续向外搜索，违反了路径必须在终点结束的要求。
  • 只统计零格而漏掉起点和终点，会使剩余计数与递归语义不一致。
  • 使用永久访问标记，会让先搜索的路径占住格子，妨碍后续合法候选。
  • 恢复时统一写成零，会改变原始起点标记；应保存并恢复进入时的原值。

相似题目

题目 难度 关联与区别
62. 不同路径 中等 不同路径系列。I 只向右或向下移动，省去访问集合后可直接按位置进行路径计数 DP。
63. 不同路径 II 中等 不同路径系列。II 保留障碍约束，但只向右或向下移动，无需覆盖全部空格，可按位置累计路径数。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/18531579
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！