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
< ? php function binomialCoeff ( $ n , $ k ) { $ res = 1 ; if ( $ k > $ n - $ k ) $ k = $ n - $ k ; for ( $ i = 0 ; $ i < $ k ; ++ $ i ) { $ res *= ( $ n - $ i ) ; $ res /= ( $ i + 1 ) ; } return $ res ; } function countPaths ( $ x1 , $ y1 , $ x2 , $ y2 ) { $ m = abs ( $ x1 - $ x2 ) ; $ n = abs ( $ y1 - $ y2 ) ; return ( binomialCoeff ( $ m + $ n , $ n ) ) ; } { $ x1 = 2 ; $ y1 = 3 ; $ x2 = 4 ; $ y2 = 5 ; echo ( countPaths ( $ x1 , $ y1 , $ x2 , $ y2 ) ) ; }