Count paths with distance equal to Manhattan distance | C ++ implementation of the approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ll  long long int NEW_LINE ll binomialCoeff ( int n , int k ) { ll res = 1 ; if ( k > n - k ) k = n - k ; for ( int i = 0 ; i < k ; ++ i ) { res *= ( n - i ) ; res /= ( i + 1 ) ; } return res ; } ll countPaths ( int x1 , int y1 , int x2 , int y2 ) { int m = abs ( x1 - x2 ) ; int n = abs ( y1 - y2 ) ; return ( binomialCoeff ( m + n , n ) ) ; } int main ( ) { int x1 = 2 , y1 = 3 , x2 = 4 , y2 = 5 ; cout << countPaths ( x1 , y1 , x2 , y2 ) ; return 0 ; }