Total number of decreasing paths in a matrix | Python3 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
MAX = 100 NEW_LINE def CountDecreasingPathsCell ( mat , dp , n , x , y ) : NEW_LINE INDENT if ( dp [ x ] [ y ] != - 1 ) : NEW_LINE INDENT return dp [ x ] [ y ] NEW_LINE DEDENT delta = [ [ 0 , 1 ] , [ 1 , 0 ] , [ - 1 , 0 ] , [ 0 , - 1 ] ] NEW_LINE newx , newy = 0 , 0 NEW_LINE ans = 1 NEW_LINE for i in range ( 4 ) : NEW_LINE INDENT newx = x + delta [ i ] [ 0 ] NEW_LINE newy = y + delta [ i ] [ 1 ] NEW_LINE if ( newx >= 0 and newx < n and newy >= 0 and newy < n and mat [ newx ] [ newy ] < mat [ x ] [ y ] ) : NEW_LINE INDENT ans += CountDecreasingPathsCell ( mat , dp , n , newx , newy ) NEW_LINE DEDENT DEDENT dp [ x ] [ y ] = ans NEW_LINE return dp [ x ] [ y ] NEW_LINE DEDENT def countDecreasingPathsMatrix ( n , mat ) : NEW_LINE INDENT dp = [ ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT l = [ ] NEW_LINE for j in range ( n ) : NEW_LINE INDENT l . append ( - 1 ) NEW_LINE DEDENT dp . append ( l ) NEW_LINE DEDENT sum = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( n ) : NEW_LINE INDENT sum += CountDecreasingPathsCell ( mat , dp , n , i , j ) NEW_LINE DEDENT DEDENT return sum NEW_LINE DEDENT n = 2 NEW_LINE mat = [ [ 1 , 2 ] , [ 1 , 3 ] ] NEW_LINE print ( countDecreasingPathsMatrix ( n , mat ) ) NEW_LINE