text: Number of ways to reach the end of matrix with non | C # implementation of the approach ; 3d array to store states of dp ; Array to determine whether a state has been solved before ; Function to return the count of required paths ; Base cases ; If a state has been solved before it won 't be evaluated again ; Recurrence relation ; Driver code
code: using System ; class GFG { static int n = 3 ; static int maxV = 20 ; static int [ , , ] dp = new int [ n , n , maxV ] ; static int [ , , ] v = new int [ n , n , maxV ] ; static int countWays ( int i , int j , int x , int [ , ] arr ) { if ( i == n j == n ) { return 0 ; } x = ( x & arr [ i , j ] ) ; if ( x == 0 ) { return 0 ; } if ( i == n - 1 && j == n - 1 ) { return 1 ; } if ( v [ i , j , x ] == 1 ) { return dp [ i , j , x ] ; } v [ i , j , x ] = 1 ; dp [ i , j , x ] = countWays ( i + 1 , j , x , arr ) + countWays ( i , j + 1 , x , arr ) ; return dp [ i , j , x ] ; } public static void Main ( ) { int [ , ] arr = { { 1 , 2 , 1 } , { 1 , 1 , 0 } , { 2 , 1 , 1 } } ; Console . WriteLine ( countWays ( 0 , 0 , arr [ 0 , 0 ] , arr ) ) ; } }