Find the longest path in a matrix with given constraints | C # program to find the longest path in a matrix with given constraints ; Function that 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 ; Function that 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 Code
using System ; class GFG { public static int n = 3 ; public static int findLongestFromACell ( int i , int j , int [ ] [ ] mat , int [ ] [ ] dp ) { if ( i < 0 i >= n j < 0 j >= n ) { return 0 ; } if ( dp [ i ] [ j ] != - 1 ) { return dp [ i ] [ j ] ; } int x = int . MinValue , y = int . MinValue , z = int . MinValue , w = int . MinValue ; if ( j < n - 1 && ( ( mat [ i ] [ j ] + 1 ) == mat [ i ] [ j + 1 ] ) ) { x = dp [ i ] [ j ] = 1 + findLongestFromACell ( i , j + 1 , mat , dp ) ; } if ( j > 0 && ( mat [ i ] [ j ] + 1 == mat [ i ] [ j - 1 ] ) ) { y = dp [ i ] [ j ] = 1 + findLongestFromACell ( i , j - 1 , mat , dp ) ; } if ( i > 0 && ( mat [ i ] [ j ] + 1 == mat [ i - 1 ] [ j ] ) ) { z = dp [ i ] [ j ] = 1 + findLongestFromACell ( i - 1 , j , mat , dp ) ; } if ( i < n - 1 && ( mat [ i ] [ j ] + 1 == mat [ i + 1 ] [ j ] ) ) { w = dp [ i ] [ j ] = 1 + findLongestFromACell ( i + 1 , j , mat , dp ) ; } dp [ i ] [ j ] = Math . Max ( x , Math . Max ( y , Math . Max ( z , Math . Max ( w , 1 ) ) ) ) ; return dp [ i ] [ j ] ; } public static int finLongestOverAll ( int [ ] [ ] mat ) { int result = 1 ; int [ ] [ ] dp = RectangularArrays . ReturnRectangularIntArray ( n , n ) ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < n ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < n ; j ++ ) { if ( dp [ i ] [ j ] == - 1 ) { findLongestFromACell ( i , j , mat , dp ) ; } result = Math . Max ( result , dp [ i ] [ j ] ) ; } } return result ; } public static class RectangularArrays { public static int [ ] [ ] ReturnRectangularIntArray ( int size1 , int size2 ) { int [ ] [ ] newArray = new int [ size1 ] [ ] ; for ( int array1 = 0 ; array1 < size1 ; array1 ++ ) { newArray [ array1 ] = new int [ size2 ] ; } return newArray ; } } public static void Main ( string [ ] args ) { int [ ] [ ] mat = new int [ ] [ ] { new int [ ] { 1 , 2 , 9 } , new int [ ] { 5 , 3 , 8 } , new int [ ] { 4 , 6 , 7 } } ; Console . WriteLine ( " Length ▁ of ▁ the ▁ longest ▁ path ▁ is ▁ " + finLongestOverAll ( mat ) ) ; } }