Easy to grasp C++ soln (with comments)


#1
int Solution::uniquePathsWithObstacles(vector<vector<int> > &A) {
    // if we see an obstacle mark dp array as 0. And all elements to its right or below it
    // will be 0 as well. We check this with flag.
    
    int M = A.size(); int N = A[0].size();
    //if(M == 1 && N == 1 && A[0][0] == 0) return 1;
    // if(A[0][0] == 1) return 0;
    
    int dp[M][N]; 
    //memset(dp, 0, sizeof dp);
    
    bool flag = false;
    // filling first row
    for(int j = 0; j<N; j++){
        if(flag || A[0][j] == 1){
            flag = true; 
            dp[0][j] = 0; // cannot be reached either cuz its after obstacle (flag)
            //or it is an obstacle itself
        }
        else dp[0][j] = 1; // path is valid (without obstacle)
    }
    flag = false;
    // filling first column
    for(int i = 0; i<M; i++){
        if(flag || A[i][0] == 1){
            flag = true; 
            dp[i][0] = 0;
        }
        else dp[i][0] = 1; 
    }
    
    for(int i = 1; i<M; i++){
        for(int j = 1; j<N; j++){
            if(A[i][j] == 1) dp[i][j] = 0; // if obstacle then 0
            else dp[i][j] = dp[i-1][j] + dp[i][j-1]; // sum of top and left ways
        }
    }
    
    return dp[M-1][N-1]; // no. of ways to reach here from top left
    
    
    
}

#2

Can you please explain the reason the reason for this comment

// return dfs(adj, visited, adj[start][i], dest); -> this is bad
        // if recursion is exhausting the call stack (big input case) instead of 
        // sending the "true" thru the call stack, just check if iteration returns true and 
        // return true to main fun.