⚡Flashcard Drill➔
NeetCode #736LC-576Medium2-D Dynamic Programming
← Back to All Problems

#736 · #576 · Out of Boundary Paths(出界的路径数)

📌 Problem Statement & Constraints

A ball sits at (startRow, startColumn) of an m x n grid. In one move it moves to one of the four adjacent cells. Return the number of distinct move sequences that take the ball out of the grid in at most maxMove moves, modulo 1e9+7. Constraints: 1 <= m, n <= 50, 0 <= maxMove <= 50, and the start cell is inside the grid.

💡 Core Algorithmic Approaches

  1. Define dp[k][i][j] = the number of paths that leave the grid starting from (i, j) with k moves remaining. The base is dp[0][i][j] = 0.
  2. For each of the four directions, if the neighbour is outside the grid the move exits immediately and contributes 1; otherwise it contributes dp[k-1][neighbour].
  3. The recurrence is dp[k][i][j] = sum over 4 neighbours (1 if outside else dp[k-1][n_i][n_j]).
  4. The answer is dp[maxMove][startRow][startColumn]; iterating k from 1 upward fills the table in maxMove layers.

💻 Benchmark Python3 Implementation

class Solution:
    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
        MOD = 10**9 + 7
        dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
        dp = [[0] * n for _ in range(m)]
        for _ in range(maxMove):
            nxt = [[0] * n for _ in range(m)]
            for i in range(m):
                for j in range(n):
                    total = 0
                    for di, dj in dirs:
                        ni, nj = i + di, j + dj
                        if 0 <= ni < m and 0 <= nj < n:
                            total += dp[ni][nj]
                        else:
                            total += 1         # this single move already exits
                    nxt[i][j] = total % MOD
            dp = nxt
        return dp[startRow][startColumn] % MOD

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(maxMove * m * n): each layer visits every cell with four constant-time transitions.
💾 Space Complexity
O(m * n): two grid layers.

⚠️ Interview Pitfalls & Follow-ups

  • Counting only paths of exactly maxMove steps: the ball may exit earlier, so exits are counted at every step via the +1 for out-of-grid neighbours.
  • Recursing without memoisation: the number of paths grows exponentially, so a plain DFS times out.
  • Forgetting the modulo on each addition: counts blow up far beyond 64 bits.
  • Reversing the DP direction: dp[k][i][j] counts paths from (i, j), which makes the base case zero and the answer a single cell lookup.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems