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 = 1_000_000_007;
    const rows = grid.length;
    const columns = grid[0].length;
    const verticalReach = Math.floor(Math.sqrt(d * d - 1));

    const rangeTotals = (values, radius) => {
        const prefix = new Array(columns + 1).fill(0);
        for (let column = 0; column < columns; column++) {
            prefix[column + 1] = (prefix[column] + values[column]) % MOD;
        }

        const totals = new Array(columns).fill(0);
        for (let column = 0; column < columns; column++) {
            const left = Math.max(0, column - radius);
            const right = Math.min(columns - 1, column + radius);
            totals[column] = (prefix[right + 1] - prefix[left] + MOD) % MOD;
        }
        return totals;
    };

    let incoming = new Array(columns).fill(0);
    for (let column = 0; column < columns; column++) {
        if (grid[rows - 1][column] === '.') {
            incoming[column] = 1;
        }
    }

    for (let row = rows - 1; row >= 0; row--) {
        const rowWays = rangeTotals(incoming, d);
        for (let column = 0; column < columns; column++) {
            if (grid[row][column] === '#') {
                rowWays[column] = 0;
            }
        }

        if (row === 0) {
            return rowWays.reduce((sum, value) => (sum + value) % MOD, 0);
        }

        incoming = rangeTotals(rowWays, verticalReach);
        for (let column = 0; column < columns; column++) {
            if (grid[row - 1][column] === '#') {
                incoming[column] = 0;
            }
        }
    }

    return 0;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

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