Out of Boundary Paths
DP Top-down Approach
Intuition :
First, we discover that there's four direction a point can go, check if it out of bound, if out-of-bound, it is a path we just find. Therefore, use dfs on it. Okay, but it will TLE without cache, so we use memoization to cache already computed value. Therefore, next time we encounter same i,j,cntMove, we only need to read dp[i][j][cntMove], for example.
Code :
cpp
int dir[5] = {0,1,0,-1,0};
int mod = 1e9+7;
int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
vector<vector<vector<int>>> dp( m+1, vector<vector<int>>(n+1, vector<int>(maxMove+1,-1)));
return dfs(m,n,startRow,startColumn,maxMove,0,dp);
}
int dfs(int m, int n, int i, int j, int maxMove, int cntMove, vector<vector<vector<int>>>& dp) {
if(cntMove == maxMove)
return 0;
if(dp[i][j][cntMove] != -1)
return dp[i][j][cntMove];
int cntRes = 0;
for(int d = 0; d < 4; d++) {
if (i+dir[d] < 0 || i+dir[d] >= m || j+dir[d+1] < 0 || j+dir[d+1] >= n)
cntRes++;
else
cntRes += dfs(m, n, i+dir[d], j+dir[d+1], maxMove, cntMove+1, dp);
cntRes %= mod;
}
return dp[i][j][cntMove] = cntRes % mod;
}Complexity Analysis
Time : O(m*n*MaxMove)
Space : O(m*n*maxMove)
DP Buttom-up Approach
Intuition :
We use dp matrix where dp[i][j][M] denotes the number of ways to reach the cell (i, j) from outside grid in atmost M moves.
Start from outside, we add them step by step, until reach maxMove.
Input: m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1
Output: 12
0,0,0 => 3,2,3 => 5,8,5 => 11,12,11
(add 4 direction value, if outOfBound add 1)Therefore at dp[startRow][startColumn][maxMove] we find 12.
Code :
cpp
const int dir[5] = {0,1,0,-1,0}, mod = 1e9+7;
int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
auto outOfBound = [&](int m, int n, int r, int c) {
return r < 0 || r >= m || c < 0 || c >= n;
};
long dp[51][51][51] = {};
for (int M = 1; M <= maxMove; M++) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
for (int d = 0; d < 4; d++) {
if(outOfBound(m,n,i+dir[d],j+dir[d+1]))
dp[i][j][M]++;
else
dp[i][j][M] += dp[i+dir[d]][j+dir[d+1]][M-1];
dp[i][j][M] %= mod;
}
}
}
}
return dp[startRow][startColumn][maxMove];
}Complexity Analysis
Time : O(m*n*MaxMove)
Space : O(m*n*maxMove)