Count paths with distance equal to Manhattan distance | Function to return the value of nCk ; Since C ( n , k ) = C ( n , n - k ) ; Calculate value of [ n * ( n - 1 ) * -- - * ( n - k + 1 ) ] / [ k * ( k - 1 ) * -- - * 1 ] ; Function to return the number of paths ; Difference between the ' x ' coordinates of the given points ; Difference between the ' y ' coordinates of the given points ; Driver code
def binomialCoeff ( n , k ) : NEW_LINE INDENT res = 1 NEW_LINE if ( k > n - k ) : NEW_LINE INDENT k = n - k NEW_LINE DEDENT for i in range ( k ) : NEW_LINE INDENT res *= ( n - i ) NEW_LINE res //= ( i + 1 ) NEW_LINE DEDENT return res NEW_LINE DEDENT def countPaths ( x1 , y1 , x2 , y2 ) : NEW_LINE INDENT m = abs ( x1 - x2 ) NEW_LINE n = abs ( y1 - y2 ) NEW_LINE return ( binomialCoeff ( m + n , n ) ) NEW_LINE DEDENT x1 , y1 , x2 , y2 = 2 , 3 , 4 , 5 NEW_LINE print ( countPaths ( x1 , y1 , x2 , y2 ) ) NEW_LINE