Total number of decreasing paths in a matrix | CPP program to count number of decreasing path in a matrix ; Function that returns the number of decreasing paths from a cell ( i , j ) ; checking if already calculated ; all possible paths ; counts the total number of paths ; In all four allowed direction . ; new co - ordinates ; Checking if not going out of matrix and next cell value is less than current cell value . ; function that returns the answer ; Function that counts the total decreasing path in the matrix ; Initialising dp [ ] [ ] to - 1. ; Calculating number of decreasing path from each cell . ; Driver Code ; function call that returns the count of decreasing paths in a matrix
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  100 NEW_LINE int CountDecreasingPathsCell ( int mat [ MAX ] [ MAX ] , int dp [ MAX ] [ MAX ] , int n , int x , int y ) { if ( dp [ x ] [ y ] != -1 ) return dp [ x ] [ y ] ; int delta [ 4 ] [ 2 ] = { { 0 , 1 } , { 1 , 0 } , { -1 , 0 } , { 0 , -1 } } ; int newx , newy ; int ans = 1 ; for ( int i = 0 ; i < 4 ; i ++ ) { newx = x + delta [ i ] [ 0 ] ; newy = y + delta [ i ] [ 1 ] ; if ( newx >= 0 && newx < n && newy >= 0 && newy < n && mat [ newx ] [ newy ] < mat [ x ] [ y ] ) { ans += CountDecreasingPathsCell ( mat , dp , n , newx , newy ) ; } } return dp [ x ] [ y ] = ans ; } int countDecreasingPathsMatrix ( int n , int mat [ MAX ] [ MAX ] ) { int dp [ MAX ] [ MAX ] ; for ( int i = 0 ; i < n ; i ++ ) for ( int j = 0 ; j < n ; j ++ ) dp [ i ] [ j ] = -1 ; int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) for ( int j = 0 ; j < n ; j ++ ) sum += CountDecreasingPathsCell ( mat , dp , n , i , j ) ; return sum ; } int main ( ) { int n = 2 ; int mat [ MAX ] [ MAX ] = { { 1 , 2 } , { 1 , 3 } } ; cout << countDecreasingPathsMatrix ( n , mat ) << endl ; return 0 ; }