出界的路径数

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

给一个 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 暂存，漏取模一溢出就废。