Out of Boundary Paths

medium dp memoization

Problem

Move at most maxMove steps from (startRow, startCol). Count paths that exit the m×n board. Return modulo 10^9+7.

Inputm=2 n=2 maxMove=2 startRow=0 startCol=0

Output6

From (0,0) with 2 moves we can exit 6 different ways.

input

def find_paths(m, n, k, r, c):
    MOD = 10**9 + 7
    from functools import lru_cache
    @lru_cache(None)
    def f(r, c, k):
        if r < 0 or r == m or c < 0 or c == n: return 1
        if k == 0: return 0
        return (f(r+1,c,k-1)+f(r-1,c,k-1)+f(r,c+1,k-1)+f(r,c-1,k-1)) % MOD
    return f(r, c, k)

function findPaths(m, n, k, r, c) {
  const MOD = 1e9 + 7; const memo = new Map();
  function f(r, c, k) {
    if (r < 0 || r === m || c < 0 || c === n) return 1;
    if (k === 0) return 0;
    const key = r + ',' + c + ',' + k;
    if (memo.has(key)) return memo.get(key);
    const v = (f(r+1,c,k-1)+f(r-1,c,k-1)+f(r,c+1,k-1)+f(r,c-1,k-1)) % MOD;
    memo.set(key, v); return v;
  }
  return f(r, c, k);
}

int findPaths(int m, int n, int K, int r, int c) {
    long[][][] dp = new long[m+2][n+2][K+1];
    for (long[][] a : dp) for (long[] b : a) Arrays.fill(b, -1);
    return (int) f(m, n, K, r, c, dp);
}
long f(int m, int n, int K, int r, int c, long[][][] dp) {
    if (r < 0 || r == m || c < 0 || c == n) return 1;
    if (K == 0) return 0;
    if (dp[r][c][K] >= 0) return dp[r][c][K];
    long MOD = 1_000_000_007L;
    return dp[r][c][K] = (f(m,n,K-1,r+1,c,dp)+f(m,n,K-1,r-1,c,dp)+f(m,n,K-1,r,c+1,dp)+f(m,n,K-1,r,c-1,dp)) % MOD;
}

int MOD = 1e9+7;
int findPaths(int m, int n, int K, int r, int c, vector>>& dp) {
    if (r < 0 || r == m || c < 0 || c == n) return 1;
    if (K == 0) return 0;
    if (dp[r][c][K] >= 0) return dp[r][c][K];
    long s = (long)findPaths(m,n,K-1,r+1,c,dp)+findPaths(m,n,K-1,r-1,c,dp)+findPaths(m,n,K-1,r,c+1,dp)+findPaths(m,n,K-1,r,c-1,dp);
    return dp[r][c][K] = s % MOD;
}

Explanation

From a starting cell on an m×n board, we make up to maxMove steps in the four directions and count how many move sequences end with the ball falling off the edge. The natural way is a recursive function f(r, c, k) = the number of ways to exit starting at (r, c) with k moves left, with results memoized so we never recompute the same state.

There are two base cases. If (r, c) is already outside the board, that is one successful exit, so return 1. If we are still on the board but have k == 0 moves left, we can't escape, so return 0.

Otherwise the answer is the sum over the four neighbors, each with one fewer move: f(r+1,c,k-1) + f(r-1,c,k-1) + f(r,c+1,k-1) + f(r,c-1,k-1), all taken mod 10^9 + 7.

Memoizing on the key (r, c, k) is what makes this efficient: there are only m · n · maxMove distinct states, so the whole thing runs in O(m·n·k).

Example: a 2×2 board with maxMove = 2 starting at (0,0) exits in 6 different ways — two immediate edge moves plus paths that step inward first and then escape.

Time: O(m·n·k) Space: O(m·n·k)