Count number of paths with at | Python3 program to count number of paths with maximum k turns allowed ; table to store results of subproblems ; Returns count of paths to reach ( i , j ) from ( 0 , 0 ) using at - most k turns . d is current direction , d = 0 indicates along row , d = 1 indicates along column . ; If invalid row or column indexes ; If current cell is top left itself ; If 0 turns left ; If direction is row , then we can reach here only if direction is row and row is 0. ; If direction is column , then we can reach here only if direction is column and column is 0. ; If this subproblem is already evaluated ; If current direction is row , then count paths for two cases 1 ) We reach here through previous row . 2 ) We reach here through previous column , so number of turns k reduce by 1. ; Similar to above if direction is column ; This function mainly initializes ' dp ' array as - 1 and calls countPathsUtil ( ) ; If ( 0 , 0 ) is target itself ; Recur for two cases : moving along row and along column ; Driver Code
MAX = 100 NEW_LINE dp = [ [ [ [ - 1 for col in range ( 2 ) ] for col in range ( MAX ) ] for row in range ( MAX ) ] for row in range ( MAX ) ] NEW_LINE def countPathsUtil ( i , j , k , d ) : NEW_LINE INDENT if ( i < 0 or j < 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( i == 0 and j == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( k == 0 ) : NEW_LINE INDENT if ( d == 0 and i == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( d == 1 and j == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT return 0 NEW_LINE DEDENT if ( dp [ i ] [ j ] [ k ] [ d ] != - 1 ) : NEW_LINE INDENT return dp [ i ] [ j ] [ k ] [ d ] NEW_LINE DEDENT if ( d == 0 ) : NEW_LINE INDENT dp [ i ] [ j ] [ k ] [ d ] = countPathsUtil ( i , j - 1 , k , d ) + countPathsUtil ( i - 1 , j , k - 1 , not d ) NEW_LINE return dp [ i ] [ j ] [ k ] [ d ] NEW_LINE DEDENT dp [ i ] [ j ] [ k ] [ d ] = countPathsUtil ( i - 1 , j , k , d ) + countPathsUtil ( i , j - 1 , k - 1 , not d ) NEW_LINE return dp [ i ] [ j ] [ k ] [ d ] NEW_LINE DEDENT def countPaths ( i , j , k ) : NEW_LINE INDENT if ( i == 0 and j == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT return countPathsUtil ( i - 1 , j , k , 1 ) + countPathsUtil ( i , j - 1 , k , 0 ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT m = 3 NEW_LINE n = 3 NEW_LINE k = 2 NEW_LINE print ( " Number ▁ of ▁ paths ▁ is " , countPaths ( m - 1 , n - 1 , k ) ) NEW_LINE DEDENT