Problem Statement in English

You’re given a grid of size m x n and a starting position (startRow, startColumn). You can move in four directions: up, down, left, and right. You can make at most maxMove moves. The goal is to find the number of paths that lead out of the grid boundaries after making exactly maxMove moves.

You need to return the number of such paths modulo $10^9 + 7$.

Approach

You’re essentially looking for the number of ways to move out of the grid after a certain number of moves. This can be solved using dynamic programming with memoization. This is also because the constraints allow for it.

Solution in Python


class Solution:
    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
        moves = [(-1,0),(0,1),(1,0),(0,-1)]

        @cache
        def dfs(i,j, steps):
            if not (0<=i<m and 0<=j<n):
                return 1
            elif not steps:
                return 0

            ans = 0
            for dx,dy in moves:
                ans+=dfs(i+dx,j+dy, steps-1)

            return ans % 1000_000_007

        return dfs(startRow,startColumn,maxMove)

Complexity

  • Time: $O(m * n * \text{maxMove})$
    Since we are using memoization, each state (i, j, steps) is computed only once.

  • Space: $O(m * n * \text{maxMove})$
    This is the space used by the memoization cache.

And we are done.