Number of ways to reach destination in the grid

Math Dynamic Programming Combinatorics

58.3% acceptance

Mar 31, 2026

You are given two integers n and m which represent the size of a 1-indexed grid. You are also given an integer k, a 1-indexed integer array source and a 1-indexed integer array dest, where source and dest are in the form [x, y] representing a cell on the given grid. You can move through the grid in the following way: You can go from cell [x1, y1] to cell [x2, y2] if either x1 == x2 or y1 == y2. Note that you can't move to the cell you are already in e.g. x1 == x2 and y1 == y2. Return the number of ways you can reach dest from source by moving through the grid exactly k times. Since the answer may be very large, return it modulo 109 + 7.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn number_of_ways(n: i32, m: i32, k: i32, source: Vec<i32>, dest: Vec<i32>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let n = n as i64;
    let m = m as i64;
    let same_row = source[0] == dest[0];
    let same_col = source[1] == dest[1];
    let init = match (same_row, same_col) {
      (true, true) => 0,
      (true, false) => 1,
      (false, true) => 2,
      (false, false) => 3,
    };
    let mut dp = [0i64; 4];
    dp[init] = 1;
    let a = m - 1;
    let b = n - 1;
    let c = m - 2;
    let d = n - 2;
    for _ in 0..k {
      let mut nd = [0i64; 4];
      nd[1] = (nd[1] + dp[0] % MOD * a % MOD) % MOD;
      nd[2] = (nd[2] + dp[0] % MOD * b % MOD) % MOD;
      nd[0] = (nd[0] + dp[1]) % MOD;
      nd[1] = (nd[1] + dp[1] % MOD * c % MOD) % MOD;
      nd[3] = (nd[3] + dp[1] % MOD * b % MOD) % MOD;
      nd[0] = (nd[0] + dp[2]) % MOD;
      nd[2] = (nd[2] + dp[2] % MOD * d % MOD) % MOD;
      nd[3] = (nd[3] + dp[2] % MOD * a % MOD) % MOD;
      nd[1] = (nd[1] + dp[3]) % MOD;
      nd[2] = (nd[2] + dp[3]) % MOD;
      nd[3] = (nd[3] + dp[3] % MOD * ((d + c) % MOD) % MOD) % MOD;
      dp = nd;
    }
    dp[0] as i32
  }
}