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)

1There are several ways to solve this problem. One way is to use a dynamic programming approach, keeping track of the number of ways to reach each position in the grid. Another way is to use combinatorics, counting the number of paths that end at each position in the grid.
2
3Here is one possible solution using dynamic programming:
4
5int outOfBoundaryPaths(int m, int n, int N, int i, int j) {
6    
7    // Create a 2D array to store the number of ways to reach each position
8    int dp[m][n];
9    
10    // Initialize all positions to 0
11    for (int x = 0; x < m; x++) {
12        for (int y = 0; y < n; y++) {
13            dp[x][y] = 0;
14        }
15    }
16    
17    // Base case: there is only one way to reach the starting position
18    dp[i][j] = 1;
19    
20    // Loop through the number of steps
21    for (int k = 0; k < N; k++) {
22        
23        // Create a 2D array to store the number of ways to reach each position in the next step
24        int next[m][n];
25        
26        // Initialize all positions to 0
27        for (int x = 0; x < m; x++) {
28            for (int y = 0; y < n; y++) {
29                next[x][y] = 0;
30            }
31        }
32        
33        // Loop through all positions in the grid
34        for (int x = 0; x < m; x++) {
35            for (int y = 0; y < n; y++) {
36                
37                // If the position is out of bounds, we can't reach it
38                if (x < 0 || x >= m || y < 0 || y >= n) {
39                    continue;
40                }
41                
42                // Otherwise, we can reach the position from the previous step if there was a path that ended there
43                if (dp[x][y] > 0) {
44                    
45                    // We can go up, down, left, or right from the current position, so add the number of ways to reach those positions
46                    next[x-1][y] += dp[x][y];
47                    next[x+1][y] += dp[x][y];
48                    next[x][y-1] += dp[x][y];
49                    next[x][y+1] += dp[x][y];
50                }
51            }
52        }
53        
54        // The next step becomes the current step
55        for (int x = 0; x < m; x++) {
56            for (int y = 0; y < n; y++) {
57                dp[x][y] = next[x][y];
58            }
59        }
60    }
61    
62    // Return the number of ways to reach the destination
63    return dp[m-1][n-1];
64}