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: using System ; class GFG { static int ans = 0 ; static void dfs ( int i , int j , int [ , ] grid , bool [ , ] vis , int z , int z_count ) { int n = grid . GetLength ( 0 ) , m = grid . GetLength ( 1 ) ; vis [ i , j ] = true ; if ( grid [ i , j ] == 0 ) z ++ ; if ( grid [ i , j ] == 2 ) { if ( z == z_count ) ans ++ ; vis [ i , j ] = false ; return ; } if ( i >= 1 && ! vis [ i - 1 , j ] && grid [ i - 1 , j ] != - 1 ) dfs ( i - 1 , j , grid , vis , z , z_count ) ; if ( i < n - 1 && ! vis [ i + 1 , j ] && grid [ i + 1 , j ] != - 1 ) dfs ( i + 1 , j , grid , vis , z , z_count ) ; if ( j >= 1 && ! vis [ i , j - 1 ] && grid [ i , j - 1 ] != - 1 ) dfs ( i , j - 1 , grid , vis , z , z_count ) ; if ( j < m - 1 && ! vis [ i , j + 1 ] && grid [ i , j + 1 ] != - 1 ) dfs ( i , j + 1 , grid , vis , z , z_count ) ; vis [ i , j ] = false ; } static int uniquePaths ( int [ , ] grid ) { int n = grid . GetLength ( 0 ) , m = grid . GetLength ( 1 ) ; bool [ , ] vis = new bool [ n , m ] ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { vis [ i , j ] = false ; } } int x = 0 , y = 0 ; 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 , 0 , z_count ) ; return ans ; } static void Main ( ) { int [ , ] grid = { { 1 , 0 , 0 , 0 } , { 0 , 0 , 0 , 0 } , { 0 , 0 , 2 , - 1 } } ; Console . WriteLine ( uniquePaths ( grid ) ) ; } }