Find length of the longest consecutive path from a given starting character | PHP program to find the longest consecutive path ; tool matrices to recur for adjacent cells . ; dp [ i ] [ j ] Stores length of longest consecutive path starting at arr [ i ] [ j ] . ; check whether mat [ i ] [ j ] is a valid cell or not . ; Check whether current character is adjacent to previous character ( character processed in parent call ) or not . ; i , j are the indices of the current cell and prev is the character processed in the parent call . . also mat [ i ] [ j ] is our current character . ; If this cell is not valid or current character is not adjacent to previous one ( e . g . d is not adjacent to b ) or if this cell is already included in the path than return 0. ; If this subproblem is already solved , return the answer ; Initialize answer ; recur for paths with different adjacent cells and store the length of longest path . ; save the answer and return ; Returns length of the longest path with all characters consecutive to each other . This function first initializes dp array that is used to store results of subproblems , then it calls recursive DFS based function getLenUtil ( ) to find max length path ; check for each possible starting point ; recur for all eight adjacent cells ; Driver code
< ? php $ R = 3 ; $ C = 3 ; $ x = array ( 0 , 1 , 1 , -1 , 1 , 0 , -1 , -1 ) ; $ y = array ( 1 , 0 , 1 , 1 , -1 , -1 , 0 , -1 ) ; $ dp = array_fill ( 0 , $ R , array_fill ( 0 , $ C , -1 ) ) ; function isvalid ( $ i , $ j ) { global $ R , $ C ; if ( $ i < 0 $ j < 0 $ i >= $ R $ j >= $ C ) return false ; return true ; } function isadjacent ( $ prev , $ curr ) { return ( ( ord ( $ curr ) - ord ( $ prev ) ) == 1 ) ; } function getLenUtil ( $ mat , $ i , $ j , $ prev ) { global $ x , $ y , $ dp ; if ( ! isvalid ( $ i , $ j ) || ! isadjacent ( $ prev , $ mat [ $ i ] [ $ j ] ) ) return 0 ; if ( $ dp [ $ i ] [ $ j ] != -1 ) return $ dp [ $ i ] [ $ j ] ; $ ans = 0 ; for ( $ k = 0 ; $ k < 8 ; $ k ++ ) $ ans = max ( $ ans , 1 + getLenUtil ( $ mat , $ i + $ x [ $ k ] , $ j + $ y [ $ k ] , $ mat [ $ i ] [ $ j ] ) ) ; $ dp [ $ i ] [ $ j ] = $ ans ; return $ ans ; } function getLen ( $ mat , $ s ) { global $ R , $ C , $ x , $ y ; $ ans = 0 ; for ( $ i = 0 ; $ i < $ R ; $ i ++ ) { for ( $ j = 0 ; $ j < $ C ; $ j ++ ) { if ( $ mat [ $ i ] [ $ j ] == $ s ) { for ( $ k = 0 ; $ k < 8 ; $ k ++ ) $ ans = max ( $ ans , 1 + getLenUtil ( $ mat , $ i + $ x [ $ k ] , $ j + $ y [ $ k ] , $ s ) ) ; } } } return $ ans ; } $ mat = array ( array ( ' a ' , ' c ' , ' d ' ) , array ( ' h ' , ' b ' , ' a ' ) , array ( ' i ' , ' g ' , ' f ' ) ) ; print ( getLen ( $ mat , ' a ' ) . " " ) ; print ( getLen ( $ mat , ' e ' ) . " " ) ; print ( getLen ( $ mat , ' b ' ) . " " ) ; print ( getLen ( $ mat , ' f ' ) . " " ) ; ? >