Find the longest path in a matrix with given constraints | Python3 program to find the longest path in a matrix with given constraints ; Returns length of the longest path beginning with mat [ i ] [ j ] . This function mainly uses lookup table dp [ n ] [ n ] ; Base case ; If this subproblem is already solved ; To store the path lengths in all the four directions ; Since all numbers are unique and in range from 1 to n * n , there is atmost one possible direction from any cell ; If none of the adjacent fours is one greater we will take 1 otherwise we will pick maximum from all the four directions ; Returns length of the longest path beginning with any cell ; Initialize result ; Create a lookup table and fill all entries in it as - 1 ; Compute longest path beginning from all cells ; Update result if needed ; Driver program
n = 3 NEW_LINE def findLongestFromACell ( i , j , mat , dp ) : NEW_LINE INDENT if ( i < 0 or i >= n or j < 0 or j >= n ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( dp [ i ] [ j ] != - 1 ) : NEW_LINE INDENT return dp [ i ] [ j ] NEW_LINE DEDENT x , y , z , w = - 1 , - 1 , - 1 , - 1 NEW_LINE if ( j < n - 1 and ( ( mat [ i ] [ j ] + 1 ) == mat [ i ] [ j + 1 ] ) ) : NEW_LINE INDENT x = 1 + findLongestFromACell ( i , j + 1 , mat , dp ) NEW_LINE DEDENT if ( j > 0 and ( mat [ i ] [ j ] + 1 == mat [ i ] [ j - 1 ] ) ) : NEW_LINE INDENT y = 1 + findLongestFromACell ( i , j - 1 , mat , dp ) NEW_LINE DEDENT if ( i > 0 and ( mat [ i ] [ j ] + 1 == mat [ i - 1 ] [ j ] ) ) : NEW_LINE INDENT z = 1 + findLongestFromACell ( i - 1 , j , mat , dp ) NEW_LINE DEDENT if ( i < n - 1 and ( mat [ i ] [ j ] + 1 == mat [ i + 1 ] [ j ] ) ) : NEW_LINE INDENT w = 1 + findLongestFromACell ( i + 1 , j , mat , dp ) NEW_LINE DEDENT dp [ i ] [ j ] = max ( x , max ( y , max ( z , max ( w , 1 ) ) ) ) NEW_LINE return dp [ i ] [ j ] NEW_LINE DEDENT def finLongestOverAll ( mat ) : NEW_LINE INDENT result = 1 NEW_LINE dp = [ [ - 1 for i in range ( n ) ] for i in range ( n ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( n ) : NEW_LINE INDENT if ( dp [ i ] [ j ] == - 1 ) : NEW_LINE INDENT findLongestFromACell ( i , j , mat , dp ) NEW_LINE DEDENT result = max ( result , dp [ i ] [ j ] ) ; NEW_LINE DEDENT DEDENT return result NEW_LINE DEDENT mat = [ [ 1 , 2 , 9 ] , [ 5 , 3 , 8 ] , [ 4 , 6 , 7 ] ] NEW_LINE print ( " Length ▁ of ▁ the ▁ longest ▁ path ▁ is ▁ " , finLongestOverAll ( mat ) ) NEW_LINE