0

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.

  • 1
    Time to learn how to use a [*debugger*](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) to catch crashes and see when and where in your code they happen. – Some programmer dude Oct 10 '22 at 10:31
  • if `i==0` then `mat[i-1][j]` will be invalid (because `i-1==-1`) same for if `j==0` – Botond Horváth Oct 10 '22 at 11:51

0 Answers0