LeetCode 576. 出界的路径数

约 5 分钟
文章信息 6 个分类 1 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 微软
标签
动态规划

题目描述

✅ 576. 出界的路径数

image-20260929101152168

image-20260929101152281

题意分析

球从网格内的起点出发，每一步可以向上下左右移动，求最多 maxMove 步内走出边界的路径数，并对 10^9 + 7 取模。一次路径在首次出界时就结束，不能在界外继续走。

不同移动顺序可以到达同一格，仍应算作不同路径；同一格也可以重复经过。因此需要记录到达次数，而不是像可达性搜索那样把格子标记为已访问。

解法：按步数滚动 DP

核心思路

[!blue]
第 step 轮开始时，dp[r][c] 表示恰好走了 step - 1 步、全程未出界且停在 (r, c) 的路径数余数。初始走零步时只有起点的一条空路径，所以起点计数为一，其余为零。

从一个格子沿某方向再走一步，原有的每条路径都会得到一种新的走法。如果新位置仍在网格内，就把 dp[r][c] 累加到 next[nr][nc]；若新位置出界，则把同样的数量加入答案。不能只加一，因为当前状态可能已经汇集了很多不同路径。

每轮使用全零的 next，只从旧层转移，确保每轮恰好多走一步。出界路径不放入下一层，因此不会继续扩展；把每一轮的出界贡献都累加，就统计了所有首次出界步数不超过 maxMove 的路径，每条恰好一次。

所有转移都是加法，可以在每次累加后取模。计数余数为零的状态即使原本存在路径，对后续余数的贡献也为零，因此可以跳过。

解题步骤

  1. 初始化起点计数为一，答案为零。
  2. 从第 1 步到第 maxMove 步逐层处理，每轮新建全零的下一层数组。
  3. 对旧层各格枚举四个方向，界内贡献加入 next，界外贡献加入答案，每次累加后取模。
  4. 用 next 替换 dp，最后返回累计出界数量。

maxMove = 0 时不会发生任何移动，答案为零；某格的多个方向都出界时，每个方向仍是不同的路径，需要分别累计。

代码实现

class Solution {
    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        int mod = 1_000_000_007;
        int[][] dp = new int[m][n];

        // 走 0 步停在起点，只有一条空路径。
        dp[startRow][startColumn] = 1;
        int answer = 0;
        int[][] dirs = {
            {0, 1},
            {0, -1},
            {1, 0},
            {-1, 0},
        };

        for (int step = 1; step <= maxMove; step++) {
            // 每轮新建全零数组，严格分离「本轮之前」与「本轮之后」的状态。
            int[][] next = new int[m][n];

            for (int r = 0; r < m; r++) {
                for (int c = 0; c < n; c++) {
                    if (dp[r][c] == 0) {
                        continue;
                    }

                    for (int[] d : dirs) {
                        int nr = r + d[0];
                        int nc = c + d[1];

                        if (nr < 0 || nr >= m || nc < 0 || nc >= n) {
                            // 出界后不写入 next，自动实现「出界即终止」。
                            answer = (answer + dp[r][c]) % mod;
                        } else {
                            next[nr][nc] = (next[nr][nc] + dp[r][c]) % mod;
                        }
                    }
                }
            }

            dp = next;
        }

        return answer;
    }
}

func findPaths(m int, n int, maxMove int, startRow int, startColumn int) int {
    const mod = 1_000_000_007
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    // 走 0 步停在起点，只有一条空路径。
    dp[startRow][startColumn] = 1

    answer := 0
    dirs := [][2]int{
        {0, 1},
        {0, -1},
        {1, 0},
        {-1, 0},
    }
    for step := 1; step <= maxMove; step++ {
        // 每轮新建全零数组，严格分离「本轮之前」与「本轮之后」的状态。
        next := make([][]int, m)
        for i := range next {
            next[i] = make([]int, n)
        }
        for r := 0; r < m; r++ {
            for c := 0; c < n; c++ {
                if dp[r][c] == 0 {
                    continue
                }
                for _, d := range dirs {
                    nr, nc := r+d[0], c+d[1]
                    if nr < 0 || nr >= m || nc < 0 || nc >= n {
                        // 出界后不写入 next，自动实现「出界即终止」。
                        answer = (answer + dp[r][c]) % mod
                    } else {
                        next[nr][nc] = (next[nr][nc] + dp[r][c]) % mod
                    }
                }
            }
        }
        dp = next
    }

    return answer
}

复杂度分析

  • 时间复杂度：$O((maxMove+1)mn)$，包含状态数组初始化。
  • 空间复杂度：$O(mn)$，只保存前后两层。

关键点总结

[!green]

  • 每次出界立即结算，后续不再扩展该路径。
  • 不同方向即使都出界，也分别代表不同走法。
  • 旧层和新层分开，确保每轮只前进一步。

易错点总结

[!yellow]

  • 界内转移直接赋值：覆盖来自其他方向的路径。
  • 出界只加一：丢失汇合在当前格的多条路径。
  • 只统计最后一步出界：漏掉更早成功的路径。
  • 返回最后界内状态之和：这些路径尚未出界，不是题目答案。

相似题目

题目 难度 关联与区别
688. 骑士在棋盘上的概率 中等 同样按步数维护棋盘状态，原题计算固定步数后仍在棋盘的概率，本题累计不超过步数上限的出界走法。
62. 不同路径 中等 同样按网格前驱累加路径数，本题允许四方向且必须增加步数维度，不能只按位置递推。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/21426690
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！