Medium

题目描述

给定一个 m × n 的网格和一个球。球的初始位置在 [startRow, startColumn]。你可以将球移动到网格中四个相邻的单元格之一（可能越过网格边界移出网格）。你最多可以对球进行 maxMove 次移动。

给定五个整数 m、n、maxMove、startRow 和 startColumn，返回将球移出网格边界的路径数量。由于答案可能非常大，请返回答案模 10^9 + 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

解题思路

这是一个经典的动态规划问题。我们需要计算从起始位置开始，在最多 maxMove 步内能够移出边界的路径数量。

核心思路：

  1. 状态定义：dp[i][j][k] 表示从位置 (i, j) 开始，用恰好 k 步移出边界的路径数量
  2. 边界条件：如果当前位置已经在边界外，说明找到了一条有效路径
  3. 状态转移：对于每个位置，尝试向四个方向移动，如果移动后出界则计数加1，否则继续递归

优化策略：

  • 使用记忆化搜索避免重复计算
  • 也可以用自底向上的DP，但记忆化搜索更直观

具体实现：

  • 对于每个位置 (i, j)，检查四个方向：上下左右
  • 如果移动后的位置越界，则找到一条路径
  • 如果移动后仍在网格内且还有剩余步数，则继续搜索
  • 使用模运算处理大数问题

这种方法时间复杂度为 O(m × n × maxMove)，空间复杂度也是 O(m × n × maxMove)。

代码实现

class Solution {
private:
    int MOD = 1e9 + 7;
    int memo[51][51][51];
    int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
public:
    int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        memset(memo, -1, sizeof(memo));
        return dfs(m, n, maxMove, startRow, startColumn);
    }
    
private:
    int dfs(int m, int n, int moves, int row, int col) {
        if (row < 0 || row >= m || col < 0 || col >= n) {
            return 1;
        }
        
        if (moves == 0) {
            return 0;
        }
        
        if (memo[row][col][moves] != -1) {
            return memo[row][col][moves];
        }
        
        long long result = 0;
        for (int i = 0; i < 4; i++) {
            int newRow = row + directions[i][0];
            int newCol = col + directions[i][1];
            result = (result + dfs(m, n, moves - 1, newRow, newCol)) % MOD;
        }
        
        memo[row][col][moves] = result;
        return result;
    }
};

class Solution:
    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
        MOD = 10**9 + 7
        memo = {}
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        def dfs(row, col, moves):
            if row < 0 or row >= m or col < 0 or col >= n:
                return 1
            
            if moves == 0:
                return 0
                
            if (row, col, moves) in memo:
                return memo[(row, col, moves)]
            
            result = 0
            for dr, dc in directions:
                new_row, new_col = row + dr, col + dc
                result = (result + dfs(new_row, new_col, moves - 1)) % MOD
            
            memo[(row, col, moves)] = result
            return result
        
        return dfs(startRow, startColumn, maxMove)

public class Solution {
    private const int MOD = 1000000007;
    private int[,,] memo;
    private int[][] directions = new int[][] {
        new int[] {-1, 0}, new int[] {1, 0}, 
        new int[] {0, -1}, new int[] {0, 1}
    };
    
    public int FindPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        memo = new int[m, n, maxMove + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k <= maxMove; k++) {
                    memo[i, j, k] = -1;
                }
            }
        }
        return DFS(m, n, maxMove, startRow, startColumn);
    }
    
    private int DFS(int m, int n, int moves, int row, int col) {
        if (row < 0 || row >= m || col < 0 || col >= n) {
            return 1;
        }
        
        if (moves == 0) {
            return 0;
        }
        
        if (memo[row, col, moves] != -1) {
            return memo[row, col, moves];
        }
        
        long result = 0;
        foreach (int[] dir in directions) {
            int newRow = row + dir[0];
            int newCol = col + dir[1];
            result = (result + DFS(m, n, moves - 1, newRow, newCol)) % MOD;
        }
        
        memo[row, col, moves] = (int)result;
        return (int)result;
    }
}

var findPaths = function(m, n, maxMove, startRow, startColumn) {
    const MOD = 1000000007;
    const memo = new Map();
    
    function dfs(row, col, moves) {
        if (row < 0 || row >= m || col < 0 || col >= n) {
            return 1;
        }
        if (moves === 0) {
            return 0;
        }
        
        const key = `${row},${col},${moves}`;
        if (memo.has(key)) {
            return memo.get(key);
        }
        
        let paths = 0;
        paths = (paths + dfs(row - 1, col, moves - 1)) % MOD;
        paths = (paths + dfs(row + 1, col, moves - 1)) % MOD;
        paths = (paths + dfs(row, col - 1, moves - 1)) % MOD;
        paths = (paths + dfs(row, col + 1, moves - 1)) % MOD;
        
        memo.set(key, paths);
        return paths;
    }
    
    return dfs(startRow, startColumn, maxMove);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(m × n × maxMove) - 每个状态最多计算一次
空间复杂度O(m × n × maxMove) - 记忆化存储的状态数量

相关题目