Sum of cost of all paths to reach a given cell in a Matrix | Python3 implementation to find the sum of cost of all paths to reach ( M , N ) ; Function for computing combination ; Function to find the factorial of N ; Loop to find the factorial of a given number ; Function for coumputing the sum of all path cost ; Loop to find the contribution of each ( i , j ) in the all possible ways ; Count number of times ( i , j ) visited ; Add the contribution of grid [ i ] [ j ] in the result ; Driver code ; Function Call
Col = 3 ; NEW_LINE def nCr ( n , r ) : NEW_LINE INDENT return fact ( n ) / ( fact ( r ) * fact ( n - r ) ) ; NEW_LINE DEDENT def fact ( n ) : NEW_LINE INDENT res = 1 ; NEW_LINE for i in range ( 2 , n + 1 ) : NEW_LINE INDENT res = res * i ; NEW_LINE DEDENT return res ; NEW_LINE DEDENT def sumPathCost ( grid , m , n ) : NEW_LINE INDENT sum = 0 ; NEW_LINE count = 0 ; NEW_LINE for i in range ( 0 , m + 1 ) : NEW_LINE INDENT for j in range ( 0 , n + 1 ) : NEW_LINE INDENT count = ( nCr ( i + j , i ) * nCr ( m + n - i - j , m - i ) ) ; NEW_LINE sum += count * grid [ i ] [ j ] ; NEW_LINE DEDENT DEDENT return sum ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT m = 2 ; NEW_LINE n = 2 ; NEW_LINE grid = [ [ 1 , 2 , 3 ] , [ 4 , 5 , 6 ] , [ 7 , 8 , 9 ] ] ; NEW_LINE print ( int ( sumPathCost ( grid , m , n ) ) ) ; NEW_LINE DEDENT