1.题目基本信息

1.1.题目描述

给你一个大小为 m x n 的网格和一个球。球的起始坐标为 [startRow, startColumn] 。你可以将球移到在四个方向上相邻的单元格内（可以穿过网格边界到达网格之外）。你 最多 可以移动 maxMove 次球。

给你五个整数 m、n、maxMove、startRow 以及 startColumn ，找出并返回可以将球移出边界的路径数量。因为答案可能非常大，返回对 109 + 7 取余 后的结果。

1.2.题目地址

https://leetcode.cn/problems/out-of-boundary-paths/description/

2.解题方法

2.1.解题思路

动态规划

2.2.解题步骤

第一步，状态定义。do[i][j][k]表示走i步到达点(j,k)的路径数

第二步，状态初始化。dp[0][startRow][startColumn]=1；当(j,k)!=(startRow,startColumn)时，dp[0][j][k]=0

第三步，状态转移。dp[i+1][j][k]=sum(dp[i][j+dr][k+dc] for dr,dc in 4个方向 if 0<=j+dr<m and 0<=k+dc<n)；如果dp[i][j][k]下一步出界，则结果变量加上dp[i][j][k]，待状态全部转移完，即可得到正确结果。

3.解题代码

python3代码

class Solution:
    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
        # 思路：动态规划
        MOD = 10 ** 9 + 7
        # 第一步，状态定义。do[i][j][k]表示走i步到达点(j,k)的路径数
        dp = [[[0] * n for _ in range(m)] for _ in range(maxMove + 1)]
        # 第二步，状态初始化。dp[0][startRow][startColumn]=1；当(j,k)!=(startRow,startColumn)时，dp[0][j][k]=0
        dp[0][startRow][startColumn] = 1
        # 第三步，状态转移。dp[i+1][j][k]=sum(dp[i][j+dr][k+dc] for dr,dc in 4个方向 if 0<=j+dr<m and 0<=k+dc<n)；如果dp[i][j][k]下一步出界，则结果变量加上dp[i][j][k]，待状态全部转移完，即可得到正确结果。
        result = 0
        for i in range(maxMove):
            for j in range(m):
                for k in range(n):
                    if dp[i][j][k] > 0:
                        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                            nr, nc = j + dr, k + dc
                            if 0 <= nr < m and 0 <= nc < n:
                                dp[i + 1][nr][nc] = (dp[i+ 1][nr][nc] + dp[i][j][k]) % MOD
                            else:
                                result = (result + dp[i][j][k]) % MOD
        return result

4.执行结果