Unique paths in a Grid with Obstacles | CPP program for the above approach ; If obstacle is at starting position ; Initializing starting position ; first row all are '1' until obstacle ; No ways to reach at this index ; first column all are '1' until obstacle ; No ways to reach at this index ; If current cell has no obstacle ; No ways to reach at this index ; returning the bottom right corner of Grid ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int uniquePathsWithObstacles ( vector < vector < int > > & A ) { int r = A . size ( ) ; int c = A [ 0 ] . size ( ) ; if ( A [ 0 ] [ 0 ] ) return 0 ; A [ 0 ] [ 0 ] = 1 ; for ( int j = 1 ; j < c ; j ++ ) { if ( A [ 0 ] [ j ] == 0 ) { A [ 0 ] [ j ] = A [ 0 ] [ j - 1 ] ; } else { A [ 0 ] [ j ] = 0 ; } } for ( int i = 1 ; i < r ; i ++ ) { if ( A [ i ] [ 0 ] == 0 ) { A [ i ] [ 0 ] = A [ i - 1 ] [ 0 ] ; } else { A [ i ] [ 0 ] = 0 ; } } for ( int i = 1 ; i < r ; i ++ ) { for ( int j = 1 ; j < c ; j ++ ) { if ( A [ i ] [ j ] == 0 ) { A [ i ] [ j ] = A [ i - 1 ] [ j ] + A [ i ] [ j - 1 ] ; } else { A [ i ] [ j ] = 0 ; } } } return A [ r - 1 ] ; } int main ( ) { vector < vector < int > > A = { { 0 , 0 , 0 } , { 0 , 1 , 0 } , { 0 , 0 , 0 } } ; cout << uniquePathsWithObstacles ( A ) << " STRNEWLINE " ; return 0 ; }