C++     Depth-First Search     Dynamic Programming     Medium     Memoization     Recursion    

Problem Statement:

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 (possibly out of the grid crossing the grid boundary). You can apply at most maxMove moves to the ball.

Given the five integers m, n, maxMove, startRow, startColumn, 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

 

Constraints:

  • 1 <= m, n <= 50
  • 0 <= maxMove <= 50
  • 0 <= startRow < m
  • 0 <= startColumn < n

Solution:

For edge and corner cells, the number of paths is the following:

 
 (startRow==0) + (startRow==m-1) + (startColumn==0) + (startColumn==n-1);

Now, starting from a location, we have to sum fndPaths for each neighbor and return the answer. We use DFS for this and we add memoization to make sure we are avoiding repeated calculation.

 
class Solution {
    int mod = 1e9+7;
    vector<vector<int>> memo  = vector<vector<int>>(3000,vector<int>(60,-1));
    vector<pair<int,int>> moves = vector<pair<int,int>>{ {-1,0},{+1,0},{0,-1},{0,+1} };
public:
    int findPaths(int m, int n, int maxMove, int startRow, int startColumn) 
    {
        if(maxMove<=0||startRow<0||startColumn<0||startRow>=m||startColumn>=n) return 0;
        int pos = startRow*n + startColumn;
        if (memo[pos][maxMove] >= 0) return memo[pos][maxMove];
        int x = (startRow==0) + (startRow==m-1) + (startColumn==0) + (startColumn==n-1);
        for (auto &move: moves)
        {
            x += findPaths(m,n,maxMove-1,startRow+move.first,startColumn+move.second);
            x %= mod;
        }
        return memo[pos][maxMove] = x;
    }
};
 
 
TC: O(m * n * N)
SC: O(m * n * N)