Count routes to climb a rectangular grid

Array Dynamic Programming Matrix Prefix Sum

24.1% acceptance

Mar 16, 2026

Count routes in grid from bottom row to top row with Euclidean distance constraint d. Moves either stay on same row or go to row directly above. Cannot stay on same row for two consecutive turns. Return count modulo 10^9 + 7.

Solution

Rust

Time O(n * m)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn number_of_routes(grid: Vec<String>, d: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let g: Vec<&[u8]> = grid.iter().map(|s| s.as_bytes()).collect();
    let n = g.len();
    let m = g[0].len();

    // max_dc: horizontal window radius (|dc| <= d means dc^2 <= d^2)
    // max_dc_up: vertical window radius (1 + dc^2 <= d^2 => dc <= d-1 for integer d)
    let max_dc = d as usize;
    let max_dc_up = (d as usize).saturating_sub(1);

    let mut ans: i64 = 0;

    // dp[c] = [can_do_horizontal_count, must_go_up_count]
    // h=0: arrived via vertical move (or start) — can expand horizontally or go up
    // h=1: arrived via horizontal move — must go up next
    let mut dp = vec![[0i64; 2]; m];

    for c in 0..m {
      if g[n - 1][c] == b'.' {
        dp[c][0] = 1;
      }
    }

    let mut prefix = vec![0i64; m + 1];

    for r in (0..n).rev() {
      // --- Horizontal expansion via prefix sum of dp[c][0] ---
      // Blocked source cells contribute 0 (dp[c][0] is 0 for blocked cells).
      // h_dp[cp] = sum(dp[c][0] for c in [cp-max_dc, cp+max_dc]) - dp[cp][0]
      prefix[0] = 0;
      for c in 0..m {
        prefix[c + 1] = (prefix[c] + dp[c][0]) % MOD;
      }
      for cp in 0..m {
        if g[r][cp] != b'.' { continue; }
        let lo = cp.saturating_sub(max_dc);
        let hi = (cp + max_dc).min(m - 1);
        let range_sum = (prefix[hi + 1] - prefix[lo] + MOD) % MOD;
        dp[cp][1] = (dp[cp][1] + range_sum - dp[cp][0] + MOD) % MOD;
      }

      // Count routes ending on row 0
      if r == 0 {
        for c in 0..m {
          ans = (ans + dp[c][0] + dp[c][1]) % MOD;
        }
      }

      // --- Vertical move via prefix sum of total[c] = dp[c][0] + dp[c][1] ---
      if r > 0 {
        prefix[0] = 0;
        for c in 0..m {
          prefix[c + 1] = (prefix[c] + dp[c][0] + dp[c][1]) % MOD;
        }
        let mut new_dp = vec![[0i64; 2]; m];
        for cp in 0..m {
          if g[r - 1][cp] != b'.' { continue; }
          let lo = cp.saturating_sub(max_dc_up);
          let hi = (cp + max_dc_up).min(m - 1);
          new_dp[cp][0] = (prefix[hi + 1] - prefix[lo] + MOD) % MOD;
        }
        dp = new_dp;
      }
    }

    ans as i32
  }
}