Count of ways to traverse a Matrix and return to origin in K steps | C ++ 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 Program
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MOD  1000000007 NEW_LINE long long dp [ 101 ] [ 101 ] [ 101 ] ; int N , M , K ; 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 ; } 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 ] ; } int main ( ) { N = 3 ; M = 3 ; K = 4 ; Initialize ( ) ; cout << CountWays ( 0 , 0 , K ) << " STRNEWLINE " ; return 0 ; }