text: Unique paths covering every non | C ++ implementation of the approach ; Function for dfs . i , j == > Current cell indexes vis == > To mark visited cells ans == > Result z == > Current count 0 s visited z_count == > Total 0 s present ; Mark the block as visited ; update the count ; If end block reached ; If path covered all the non - obstacle blocks ; Up ; Down ; Left ; Right ; Unmark the block ( unvisited ) ; Function to return the count of the unique paths ; int z_count = 0 ; Total 0 s present ; Count non - obstacle blocks ; Starting position ; Driver code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; void dfs ( int i , int j , vector < vector < int > > & grid , vector < vector < bool > > & vis , int & ans , int z , int z_count ) { int n = grid . size ( ) , m = grid [ 0 ] . size ( ) ; vis [ i ] [ j ] = 1 ; if ( grid [ i ] [ j ] == 0 ) z ++ ; if ( grid [ i ] [ j ] == 2 ) { if ( z == z_count ) ans ++ ; vis [ i ] [ j ] = 0 ; return ; } if ( i >= 1 && ! vis [ i - 1 ] [ j ] && grid [ i - 1 ] [ j ] != -1 ) dfs ( i - 1 , j , grid , vis , ans , z , z_count ) ; if ( i < n - 1 && ! vis [ i + 1 ] [ j ] && grid [ i + 1 ] [ j ] != -1 ) dfs ( i + 1 , j , grid , vis , ans , z , z_count ) ; if ( j >= 1 && ! vis [ i ] [ j - 1 ] && grid [ i ] [ j - 1 ] != -1 ) dfs ( i , j - 1 , grid , vis , ans , z , z_count ) ; if ( j < m - 1 && ! vis [ i ] [ j + 1 ] && grid [ i ] [ j + 1 ] != -1 ) dfs ( i , j + 1 , grid , vis , ans , z , z_count ) ; vis [ i ] [ j ] = 0 ; } int uniquePaths ( vector < vector < int > > & grid ) { int n = grid . size ( ) , m = grid [ 0 ] . size ( ) ; int ans = 0 ; vector < vector < bool > > vis ( n , vector < bool > ( m , 0 ) ) ; int x , y ; for ( int i = 0 ; i < n ; ++ i ) { for ( int j = 0 ; j < m ; ++ j ) { if ( grid [ i ] [ j ] == 0 ) z_count ++ ; else if ( grid [ i ] [ j ] == 1 ) { x = i , y = j ; } } } dfs ( x , y , grid , vis , ans , 0 , z_count ) ; return ans ; } int main ( ) { vector < vector < int > > grid { { 1 , 0 , 0 , 0 } , { 0 , 0 , 0 , 0 } , { 0 , 0 , 2 , -1 } } ; cout << uniquePaths ( grid ) ; return 0 ; }