I was following "take you forward" DP series on YouTube and trying to solve the question: https://www.codingninjas.com/codestudio/problems/maze-obstacles_977241
Before jumping to the solution of the problem from the video https://www.youtube.com/watch?v=TmhpgXScLyY&list=PLgUwDviBIf0qUlt5H_kiKYaNSqJ81PMMY&index=10&ab_channel=takeUforward, I tried the problem by myself. I came up with my solution given below. In the video, he checked a present cell whether it is 0 or -1, but I in my solution, checked the next cell(up or left, starting from the rightmost corner) whether it is 1 or -1.
Solution in video:
int solve(int i, int j, vector< vector<int>> &mat)
{
if(i>=0 && j>=0 && mat[i][j]==-1) return 0;
if(i==0 && j==0) return 1;
if(i<0 || j<0) return 0;
int up=solve(i-1,j,mat);
int left+=solve(i,j-1,mat);
return (up+left);
}
int mazeObstacles(int n, int m, vector< vector< int> > &mat) {
return solve(n-1,m-1,mat);
}
My Solution:
int solve(int i, int j, vector< vector<int>> &mat){
if(i==0 && j==0) return 1;
if(i<0 || j<0) return 0;
int up=0;
if(mat[i-1][j]!=-1) up+=solve(i-1,j,mat);
int left=0;
if(mat[i][j-1]!=-1) left+=solve(i,j-1,mat);
return (up+left);
}
int mazeObstacles(int n, int m, vector< vector< int> > &mat) {
return solve(n-1,m-1,mat);
}
My solution gave me segmentation fault. I know my approach is recursive, thus this further give me TLE, but I want to check whether my approach is correct or not, or where I'm making mistake. Please help me out with this.