Count of ways to traverse a Matrix and return to origin in K steps | Java program to count total number of ways to return to origin after completing given number of steps . ; Function Initialize dp [ ] [ ] [ ] array with - 1 ; Function returns the total count ; Driver code
class GFG { static int [ ] [ ] [ ] dp = new int [ 101 ] [ 101 ] [ 101 ] ; static int N , M , K ; static int MOD = 1000000007 ; public static void Initialize ( ) { for ( int i = 0 ; i <= 100 ; i ++ ) for ( int j = 0 ; j <= 100 ; j ++ ) for ( int z = 0 ; z <= 100 ; z ++ ) dp [ i ] [ j ] [ z ] = - 1 ; } public static int CountWays ( int i , int j , int k ) { if ( i >= N i < 0 j >= M j < 0 k < 0 ) return 0 ; if ( i == 0 && j == 0 && k == 0 ) return 1 ; if ( dp [ i ] [ j ] [ k ] != - 1 ) return dp [ i ] [ j ] [ k ] ; else dp [ i ] [ j ] [ k ] = ( CountWays ( i + 1 , j , k - 1 ) % MOD + CountWays ( i - 1 , j , k - 1 ) % MOD + CountWays ( i , j - 1 , k - 1 ) % MOD + CountWays ( i , j + 1 , k - 1 ) % MOD + CountWays ( i , j , k - 1 ) % MOD ) % MOD ; return dp [ i ] [ j ] [ k ] ; } public static void main ( String [ ] args ) { N = 3 ; M = 3 ; K = 4 ; Initialize ( ) ; System . out . println ( CountWays ( 0 , 0 , K ) ) ; } }