出界的路径数 图解题解

球在网格里怎么走才算一条出界路径

给一个 m 行 n 列网格，球在起点 (startRow, startColumn)，每步往上下左右挪一格。问最多走 maxMove 步内有多少条路径把球带出边界。路径数涨得极快、会大到变量存不下，所以答案对 1000000007 取模（除以它取余数）。题面例子 m=2、n=2、maxMove=2、起点 (0,0)，答案 6。数的是出界路径不是格子，同一位置走法不同算不同路径。

为什么把每条走法都试一遍会爆炸

最直接是从起点递归（函数自己调用自己去处理下一步）枚举每条走法，往四个方向试一遍，步数用完或出界就停。可每步分四个岔，走 maxMove 步就是 4 的 maxMove 次方条路径，maxMove 到几十就数不完。而且绕到同一格子、剩步数一样时往后能出界多少条是相同子问题，却被反复重算。记下「某格子加剩余步数」复用就能压平。

dp[r][c] 存什么，为什么按步数分层

记每个格子上攒了多少条到达它的路径。定义 dp[r][c] 为走若干步后恰好停在 (r,c) 的路径数。一开始球在起点没走，dp[startRow][startColumn]=1，其余为 0。

关键是按步数分层推进（一步一层、算完这步整张网格再算下步）。走满 k 步那层 dp 只由走满 k−1 步那层推出，与更早层无关，路径长度被步数锁死，不会串层。

每步怎么扩散，出界那一下如何计入答案

每走一步，把这层 dp 每个格子往四个方向摊开：走到界内邻居 (nr,nc) 就把 dp[r][c] 累加进新一层 ndp[nr][nc]；走到界外正好出界，把 dp[r][c] 条路径加进 ans。四方向摊完，用 ndp 覆盖 dp 进下一步。

必须用独立的 ndp 接结果，不能在 dp 上原地改——否则刚更新的格子会在同一步里又被当成源头二次扩散，等于一步走了两格。累加还要随手取模，哪几步见末节。

拿 m=2、n=2、maxMove=2 亲手扩两步

初始 dp 只有 dp[0][0]=1，ans=0。第 1 步 dp[0][0] 往下界内 (1,0)、往右界内 (0,1) 各让 ndp 记 1，往上往左两次出界 ans=2。这步完 dp 只剩 (0,1)、(1,0) 为 1。

第 2 步：dp[0][1] 往下(1,1)、往左(0,0)各进 ndp，往上往右各出界 ans 到 4；dp[1][0] 往上(0,0)、往右(1,1)各进 ndp，往下往左各出界 ans 到 6。两步走满 ans=6，和题面对上；dp 剩的非零格是停界内没出去的路径，不算数。

1×1 一步为什么是 4，取模在哪几步做

每步遍历整张 m×n 网格、每格看 4 个方向，共 maxMove 步，时间 O(maxMove·m·n)。空间只需 dp、ndp 两张网格轮换，O(m·n)，不必存每步网格。

两个边界要盯住。一是极小网格 m=1、n=1、maxMove=1：起点四个方向全在界外，一步贡献 4 条路径，答案 4。二是防溢出（数大到超出变量能存范围）：ans 和 ndp 累加都对 1000000007 取模、用 long 暂存，漏取模一溢出就废。

Python

class Solution:
    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
        MOD = 10**9 + 7
        dp = [[0] * n for _ in range(m)]
        dp[startRow][startColumn] = 1
        ans = 0
        for _ in range(maxMove):
            ndp = [[0] * n for _ in range(m)]
            for r in range(m):
                for c in range(n):
                    if dp[r][c]:
                        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                            nr, nc = r + dr, c + dc
                            if nr < 0 or nr >= m or nc < 0 or nc >= n:
                                ans = (ans + dp[r][c]) % MOD
                            else:
                                ndp[nr][nc] = (ndp[nr][nc] + dp[r][c]) % MOD
            dp = ndp
        return ans

C++

#include <vector>
using namespace std;
class Solution {
public:
    int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        const int MOD = 1000000007;
        vector<vector<int>> dp(m, vector<int>(n));
        dp[startRow][startColumn] = 1;
        long long ans = 0;
        int dirs[5] = {1,0,-1,0,1};
        for (int step = 0; step < maxMove; ++step) {
            vector<vector<int>> ndp(m, vector<int>(n));
            for (int r = 0; r < m; ++r) for (int c = 0; c < n; ++c) if (dp[r][c]) {
                for (int d = 0; d < 4; ++d) {
                    int nr = r + dirs[d], nc = c + dirs[d+1];
                    if (nr < 0 || nr >= m || nc < 0 || nc >= n) ans = (ans + dp[r][c]) % MOD;
                    else ndp[nr][nc] = (ndp[nr][nc] + dp[r][c]) % MOD;
                }
            }
            dp.swap(ndp);
        }
        return ans;
    }
};

Java

import java.util.*;
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];
        dp[startRow][startColumn] = 1;
        long ans = 0;
        int[] dirs = {1,0,-1,0,1};
        for (int step = 0; step < maxMove; step++) {
            int[][] ndp = new int[m][n];
            for (int r = 0; r < m; r++) for (int c = 0; c < n; c++) if (dp[r][c] != 0) {
                for (int d = 0; d < 4; d++) {
                    int nr = r + dirs[d], nc = c + dirs[d+1];
                    if (nr < 0 || nr >= m || nc < 0 || nc >= n) ans = (ans + dp[r][c]) % MOD;
                    else ndp[nr][nc] = (ndp[nr][nc] + dp[r][c]) % MOD;
                }
            }
            dp = ndp;
        }
        return (int) ans;
    }
}