Out Of Boundary Paths - Leetcode Solution

Problem description:

There is an m x n grid with a ball. The ball is initially at the position [startRow, startColumn]. You are allowed to move the ball to one of the four adjacent cells in the grid (up, down, left, or right) provided the next cell is empty. The ball can't move to a cell occupied by the wall. A fence is placed outside the grid on all sides. The ball is lost if it passes through the fence on any side, i.e., if startRow < 0, startRow >= m, startColumn < 0, or startColumn >= n.

Return the number of paths to move the ball out of the grid boundary. Since the answer can be very large, return it modulo 109 + 7.

Example 1:

Input: m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0 Output: 6

Example 2:

Input: m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1 Output: 12

Solution:

This problem can be solved by using dynamic programming. We can use a 3D array to store the number of ways to move the ball from each cell to the boundary. The third dimension represents the number of moves left.

1. Initialize a 3D array dp[m][n][maxMove+1], a variable res to store the result, and a variable mod to store the modulo value.

2. For each cell, calculate the number of ways to move the ball to the boundary. The boundary cells can be initialized to 1, and the non-boundary cells can be initialized to 0.

3. Use dynamic programming to fill the dp array. For each cell, the number of ways to move the ball from that cell to the boundary with k moves left can be calculated as the sum of the number of ways to move the ball from the adjacent cells to the boundary with k-1 moves left. The ball cannot move to a cell occupied by the wall.

4. Finally, add up the number of ways to move the ball from each cell to the boundary with maxMove moves left.

5. Return the result modulo mod.

Code:

The code for solving this problem in python is as follows:

class Solution(object):
    def findPaths(self, m, n, maxMove, startRow, startColumn):
        """
        :type m: int
        :type n: int
        :type maxMove: int
        :type startRow: int
        :type startColumn: int
        :rtype: int
        """
        dp = [[[0] * (maxMove + 1) for _ in range(n)] for _ in range(m)]
        mod = 10 ** 9 + 7
        res = 0
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        for i in range(m):
            for j in range(n):
                if i == 0 or i == m - 1 or j == 0 or j == n - 1:
                    dp[i][j][0] = 1

        for k in range(1, maxMove + 1):
            for i in range(m):
                for j in range(n):
                    for d in dirs:
                        ni, nj = i + d[0], j + d[1]
                        if ni < 0 or ni >= m or nj < 0 or nj >= n:
                            continue
                        dp[i][j][k] = (dp[i][j][k] + dp[ni][nj][k - 1]) % mod

        for k in range(1, maxMove + 1):
            res = (res + dp[startRow][startColumn][k]) % mod

        return res

Time Complexity: O(mnmaxMove)

Space Complexity: O(mnmaxMove)

1