Sum of cost of all paths to reach a given cell in a Matrix | C ++ 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
#include <iostream> NEW_LINE using namespace std ; const int Col = 3 ; int fact ( int n ) ; int nCr ( int n , int r ) { return fact ( n ) / ( fact ( r ) * fact ( n - r ) ) ; } int fact ( int n ) { int res = 1 ; for ( int i = 2 ; i <= n ; i ++ ) res = res * i ; return res ; } int sumPathCost ( int grid [ ] [ Col ] , int m , int n ) { int sum = 0 , count ; for ( int i = 0 ; i <= m ; i ++ ) { for ( int j = 0 ; j <= n ; j ++ ) { count = nCr ( i + j , i ) * nCr ( m + n - i - j , m - i ) ; sum += count * grid [ i ] [ j ] ; } } return sum ; } int main ( ) { int m = 2 ; int n = 2 ; int grid [ ] [ Col ] = { { 1 , 2 , 3 } , { 4 , 5 , 6 } , { 7 , 8 , 9 } } ; cout << sumPathCost ( grid , m , n ) ; return 0 ; }