Find length of the longest consecutive path from a given starting character | C ++ 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 program
#include <bits/stdc++.h> NEW_LINE #define R  3 NEW_LINE #define C  3 NEW_LINE using namespace std ; int x [ ] = { 0 , 1 , 1 , -1 , 1 , 0 , -1 , -1 } ; int y [ ] = { 1 , 0 , 1 , 1 , -1 , -1 , 0 , -1 } ; int dp [ R ] [ C ] ; bool isvalid ( int i , int j ) { if ( i < 0 j < 0 i > = R j > = C ) return false ; return true ; } bool isadjacent ( char prev , char curr ) { return ( ( curr - prev ) == 1 ) ; } int getLenUtil ( char mat [ R ] [ C ] , int i , int j , char prev ) { if ( ! isvalid ( i , j ) || ! isadjacent ( prev , mat [ i ] [ j ] ) ) return 0 ; if ( dp [ i ] [ j ] != -1 ) return dp [ i ] [ j ] ; int ans = 0 ; for ( int k = 0 ; k < 8 ; k ++ ) ans = max ( ans , 1 + getLenUtil ( mat , i + x [ k ] , j + y [ k ] , mat [ i ] [ j ] ) ) ; return dp [ i ] [ j ] = ans ; } int getLen ( char mat [ R ] [ C ] , char s ) { memset ( dp , -1 , sizeof dp ) ; int ans = 0 ; for ( int i = 0 ; i < R ; i ++ ) { for ( int j = 0 ; j < C ; j ++ ) { if ( mat [ i ] [ j ] == s ) { for ( int k = 0 ; k < 8 ; k ++ ) ans = max ( ans , 1 + getLenUtil ( mat , i + x [ k ] , j + y [ k ] , s ) ) ; } } } return ans ; } int main ( ) { char mat [ R ] [ C ] = { { ' a ' , ' c ' , ' d ' } , { ' h ' , ' b ' , ' a ' } , { ' i ' , ' g ' , ' f ' } } ; cout << getLen ( mat , ' a ' ) << endl ; cout << getLen ( mat , ' e ' ) << endl ; cout << getLen ( mat , ' b ' ) << endl ; cout << getLen ( mat , ' f ' ) << endl ; return 0 ; }