Find length of the longest consecutive path from a given starting character | Python3 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
R = 3 NEW_LINE C = 3 NEW_LINE x = [ 0 , 1 , 1 , - 1 , 1 , 0 , - 1 , - 1 ] NEW_LINE y = [ 1 , 0 , 1 , 1 , - 1 , - 1 , 0 , - 1 ] NEW_LINE dp = [ [ 0 for i in range ( C ) ] for i in range ( R ) ] NEW_LINE def isvalid ( i , j ) : NEW_LINE INDENT if ( i < 0 or j < 0 or i >= R or j >= C ) : NEW_LINE INDENT return False NEW_LINE DEDENT return True NEW_LINE DEDENT def isadjacent ( prev , curr ) : NEW_LINE INDENT if ( ord ( curr ) - ord ( prev ) ) == 1 : NEW_LINE INDENT return True NEW_LINE DEDENT return False NEW_LINE DEDENT def getLenUtil ( mat , i , j , prev ) : NEW_LINE INDENT if ( isvalid ( i , j ) == False or isadjacent ( prev , mat [ i ] [ j ] ) == False ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( dp [ i ] [ j ] != - 1 ) : NEW_LINE INDENT return dp [ i ] [ j ] NEW_LINE DEDENT ans = 0 NEW_LINE for k in range ( 8 ) : NEW_LINE INDENT ans = max ( ans , 1 + getLenUtil ( mat , i + x [ k ] , j + y [ k ] , mat [ i ] [ j ] ) ) NEW_LINE DEDENT dp [ i ] [ j ] = ans NEW_LINE return dp [ i ] [ j ] NEW_LINE DEDENT def getLen ( mat , s ) : NEW_LINE INDENT for i in range ( R ) : NEW_LINE INDENT for j in range ( C ) : NEW_LINE INDENT dp [ i ] [ j ] = - 1 NEW_LINE DEDENT DEDENT ans = 0 NEW_LINE for i in range ( R ) : NEW_LINE INDENT for j in range ( C ) : NEW_LINE INDENT if ( mat [ i ] [ j ] == s ) : NEW_LINE INDENT for k in range ( 8 ) : NEW_LINE INDENT ans = max ( ans , 1 + getLenUtil ( mat , i + x [ k ] , j + y [ k ] , s ) ) ; NEW_LINE DEDENT DEDENT DEDENT DEDENT return ans NEW_LINE DEDENT mat = [ [ ' a ' , ' c ' , ' d ' ] , [ ' h ' , ' b ' , ' a ' ] , [ ' i ' , ' g ' , ' f ' ] ] NEW_LINE print ( getLen ( mat , ' a ' ) ) NEW_LINE print ( getLen ( mat , ' e ' ) ) NEW_LINE print ( getLen ( mat , ' b ' ) ) NEW_LINE print ( getLen ( mat , ' f ' ) ) NEW_LINE