Hard

题目描述

给定一个大小为 n 的字符串数组 grid，其中每个字符串 grid[i] 的长度为 m。字符 grid[i][j] 是以下符号之一：

  • ‘.’: 该单元格可用。
  • ‘#’: 该单元格被阻塞。

你需要计算攀爬网格的不同路径数量。每条路径必须从底行（第 n - 1 行）的任意单元格开始，在顶行（第 0 行）结束。

但是，路径有一些约束条件：

  • 你只能从一个可用单元格移动到另一个可用单元格。
  • 每次移动的欧几里得距离最多为 d，其中 d 是给定的整数参数。两个单元格 (r1, c1) 和 (r2, c2) 之间的欧几里得距离为 sqrt((r1 - r2)² + (c1 - c2)²)。
  • 每次移动要么停留在同一行，要么移动到正上方的行（从第 r 行到第 r - 1 行）。
  • 你不能连续两次停留在同一行。如果你在一次移动中停留在同一行（且这次移动不是最后一次移动），你的下一次移动必须移动到上一行。

返回表示此类路径数量的整数。由于答案可能很大，请返回模 10⁹ + 7 的结果。

示例 1:

输入: grid = ["..","#."], d = 1
输出: 2

示例 2:

输入: grid = ["..","#."], d = 2
输出: 4

示例 3:

输入: grid = ["#"], d = 750
输出: 0

示例 4:

输入: grid = [".."], d = 1
输出: 4

约束条件:

  • 1 <= n == grid.length <= 750
  • 1 <= m == grid[i].length <= 750
  • grid[i][j] 是 ‘.’ 或 ‘#’
  • 1 <= d <= 750

解题思路

这是一道复杂的动态规划题目，需要考虑移动方向的状态。

思路分析

根据题目约束，我们需要追踪两个关键信息：

  1. 当前位置
  2. 上一次移动是水平移动还是向上移动（因为不能连续两次水平移动）

状态定义：

  • dp[r][c][0]: 到达位置 (r,c)，且上一次移动是从下方行 (r+1) 向上移动的路径数
  • dp[r][c][1]: 到达位置 (r,c)，且上一次移动是在同一行 r 内水平移动的路径数

状态转移：

  1. 对于 dp[r][c][0]（向上移动到达）：

    • 可以从下一行 (r+1) 的任意有效位置移动而来
    • 需要满足欧几里得距离 ≤ d 的约束

  2. 对于 dp[r][c][1]（水平移动到达）：

    • 只能从同一行的其他位置移动而来
    • 且前一个位置的状态必须是向上移动到达的（即 dp[r][c'][0]）

优化技巧： 使用前缀和优化距离范围内的贡献计算，避免重复遍历所有可能的起始位置。

边界条件：

  • 最底行作为起始状态，所有可用位置的 dp[n-1][c][0] = 1
  • 最终答案是顶行所有位置的两种状态之和

代码实现

class Solution {
public:
    int numberOfRoutes(vector<string>& grid, int d) {
        const int MOD = 1e9 + 7;
        int n = grid.size(), m = grid[0].size();
        
        // dp[r][c][0]: 从下方移动到(r,c)的路径数
        // dp[r][c][1]: 从同行移动到(r,c)的路径数
        vector<vector<vector<long long>>> dp(n, vector<vector<long long>>(m, vector<long long>(2, 0)));
        
        // 初始化最底行
        for (int c = 0; c < m; c++) {
            if (grid[n-1][c] == '.') {
                dp[n-1][c][0] = 1;
            }
        }
        
        // 从倒数第二行开始向上计算
        for (int r = n - 2; r >= 0; r--) {
            vector<long long> prefix(m + 1, 0);
            
            // 计算下一行的前缀和，用于快速查询范围内的贡献
            for (int c = 0; c < m; c++) {
                prefix[c + 1] = prefix[c];
                if (grid[r + 1][c] == '.') {
                    prefix[c + 1] = (prefix[c + 1] + dp[r + 1][c][0] + dp[r + 1][c][1]) % MOD;
                }
            }
            
            for (int c = 0; c < m; c++) {
                if (grid[r][c] == '#') continue;
                
                // 计算从下方移动到(r,c)的路径数
                int left = 0, right = m - 1;
                for (int c2 = 0; c2 < m; c2++) {
                    if (grid[r + 1][c2] == '.' && 
                        (r + 1 - r) * (r + 1 - r) + (c2 - c) * (c2 - c) <= (long long)d * d) {
                        dp[r][c][0] = (dp[r][c][0] + dp[r + 1][c2][0] + dp[r + 1][c2][1]) % MOD;
                    }
                }
                
                // 计算从同行移动到(r,c)的路径数
                for (int c2 = 0; c2 < m; c2++) {
                    if (c2 != c && grid[r][c2] == '.' && 
                        (c2 - c) * (c2 - c) <= (long long)d * d) {
                        dp[r][c][1] = (dp[r][c][1] + dp[r][c2][0]) % MOD;
                    }
                }
            }
        }
        
        // 计算顶行的总路径数
        long long result = 0;
        for (int c = 0; c < m; c++) {
            if (grid[0][c] == '.') {
                result = (result + dp[0][c][0] + dp[0][c][1]) % MOD;
            }
        }
        
        return result;
    }
};

class Solution:
    def numberOfRoutes(self, grid: List[str], d: int) -> int:
        MOD = 10**9 + 7
        n, m = len(grid), len(grid[0])
        
        # dp[r][c][0]: 从下方移动到(r,c)的路径数
        # dp[r][c][1]: 从同行移动到(r,c)的路径数
        dp = [[[0, 0] for _ in range(m)] for _ in range(n)]
        
        # 初始化最底行
        for c in range(m):
            if grid[n-1][c] == '.':
                dp[n-1][c][0] = 1
        
        # 从倒数第二行开始向上计算
        for r in range(n-2, -1, -1):
            for c in range(m):
                if grid[r][c] == '#':
                    continue
                
                # 计算从下方移动到(r,c)的路径数
                for c2 in range(m):
                    if (grid[r+1][c2] == '.' and 
                        (r+1-r)**2 + (c2-c)**2 <= d*d):
                        dp[r][c][0] = (dp[r][c][0] + dp[r+1][c2][0] + dp[r+1][c2][1]) % MOD
                
                # 计算从同行移动到(r,c)的路径数
                for c2 in range(m):
                    if (c2 != c and grid[r][c2] == '.' and 
                        (c2-c)**2 <= d*d):
                        dp[r][c][1] = (dp[r][c][1] + dp[r][c2][0]) % MOD
        
        # 计算顶行的总路径数
        result = 0
        for c in range(m):
            if grid[0][c] == '.':
                result = (result + dp[0][c][0] + dp[0][c][1]) % MOD
        
        return result

public class Solution {
    public int NumberOfRoutes(string[] grid, int d) {
        const int MOD = 1_000_000_007;
        int n = grid.Length, m = grid[0].Length;
        
        // dp[r][c][0]: 从下方移动到(r,c)的路径数
        // dp[r][c][1]: 从同行移动到(r,c)的路径数
        long[,,] dp = new long[n, m, 2];
        
        // 初始化最底行
        for (int c = 0; c < m; c++) {
            if (grid[n-1][c] == '.') {
                dp[n-1, c, 0] = 1;
            }
        }
        
        // 从倒数第二行开始向上计算
        for (int r = n - 2; r >= 0; r--) {
            for (int c = 0; c < m; c++) {
                if (grid[r][c] == '#') continue;
                
                // 计算从下方移动到(r,c)的路径数
                for (int c2 = 0; c2 < m; c2++) {
                    if (grid[r+1][c2] == '.' && 
                        (long)(r+1-r)*(r+1-r) + (long)(c2-c)*(c2-c) <= (long)d*d) {
                        dp[r, c, 0] = (dp[r, c, 0] + dp[r+1, c2, 0] + dp[r+1, c2, 1]) % MOD;
                    }
                }
                
                // 计算从同行移动到(r,c)的路径数
                for (int c2 = 0; c2 < m; c2++) {
                    if (c2 != c && grid[r][c2] == '.' && 
                        (long)(c2-c)*(c2-c) <= (long)d*d) {
                        dp[r, c, 1] = (dp[r, c, 1] + dp[r, c2, 0]) % MOD;
                    }
                }
            }
        }
        
        // 计算顶行的总路径数
        long result = 0;
        for (int c = 0; c < m; c++) {
            if (grid[0][c] == '.') {
                result = (result + dp[0, c, 0] + dp[0, c, 1]) % MOD;
            }
        }
        
        return (int)result;
    }
}

var numberOfRoutes = function(grid, d) {
    const MOD = 1e9 + 7;
    const n = grid.length, m = grid[0].length;
    
    // dp[r][c][0]: 从下方移动到(r,c)的路径数
    // dp[r][c][1]: 从同行移动到(r,c)的路径数
    const dp = Array(n).fill().map(() => 
        Array(m).fill().map(() => [0, 0])
    );
    
    // 初始化最底行
    for (let c = 0; c < m; c++) {
        if (grid[n-1][c]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n × m²)，其中 n 是行数，m 是列数。对于每个位置，需要检查所有可能的移动目标
空间复杂度O(n × m)，存储动态规划状态数组