Total number of decreasing paths in a matrix | Javascript 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
var MAX = 100 function CountDecreasingPathsCell ( mat , dp , n , x , y ) { if ( dp [ x ] [ y ] != - 1 ) return dp [ x ] [ y ] ; var delta = [ [ 0 , 1 ] , [ 1 , 0 ] , [ - 1 , 0 ] , [ 0 , - 1 ] ] ; var newx , newy ; var ans = 1 ; for ( var 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 ) ; } } dp [ x ] [ y ] = ans ; return ans ; } function countDecreasingPathsMatrix ( n , mat ) { var dp = Array . from ( Array ( MAX ) , ( ) => Array ( MAX ) ) ; for ( var i = 0 ; i < n ; i ++ ) for ( var j = 0 ; j < n ; j ++ ) dp [ i ] [ j ] = - 1 ; var sum = 0 ; for ( var i = 0 ; i < n ; i ++ ) for ( var j = 0 ; j < n ; j ++ ) sum += CountDecreasingPathsCell ( mat , dp , n , i , j ) ; return sum ; } var n = 2 ; var mat = [ [ 1 , 2 ] , [ 1 , 3 ] ] ; document . write ( countDecreasingPathsMatrix ( n , mat ) ) ;