0576：出界的路径数（★）

力扣第 576 题

题目

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

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

示例 1：

输入：m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0
输出：6

示例 2：

输入：m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1
输出：12

提示：

• 1 <= m, n <= 50
• 0 <= maxMove <= 50
• 0 <= startRow < m
• 0 <= startColumn < n

相似问题：

• 0688：骑士在棋盘上的概率
• 2120：执行所有后缀指令（1379 分）

分析

按第一步移动方向即可递归。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
        @cache
        def dfs(i,j,k):
            if not (0<=i<m and 0<=j<n):
                return 1
            if k==0:
                return 0
            return sum(dfs(x,y,k-1) for x,y in [(i,j+1),(i+1,j),(i-1,j),(i,j-1)])%mod
        mod = 10**9+7
        return dfs(startRow,startColumn,maxMove)

113 ms