Count of ways to traverse a Matrix and return to origin in K steps | Python3 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
MOD = 1000000007 NEW_LINE dp = [ [ [ 0 for i in range ( 101 ) ] for i in range ( 101 ) ] for i in range ( 101 ) ] NEW_LINE N , M , K = 0 , 0 , 0 NEW_LINE def Initialize ( ) : NEW_LINE INDENT for i in range ( 101 ) : NEW_LINE INDENT for j in range ( 101 ) : NEW_LINE INDENT for z in range ( 101 ) : NEW_LINE INDENT dp [ i ] [ j ] [ z ] = - 1 NEW_LINE DEDENT DEDENT DEDENT DEDENT def CountWays ( i , j , k ) : NEW_LINE INDENT if ( i >= N or i < 0 or j >= M or j < 0 or k < 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( i == 0 and j == 0 and k == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( dp [ i ] [ j ] [ k ] != - 1 ) : NEW_LINE INDENT return dp [ i ] [ j ] [ k ] NEW_LINE DEDENT else : NEW_LINE INDENT 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 NEW_LINE DEDENT return dp [ i ] [ j ] [ k ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 3 NEW_LINE M = 3 NEW_LINE K = 4 NEW_LINE Initialize ( ) NEW_LINE print ( CountWays ( 0 , 0 , K ) ) NEW_LINE DEDENT