Find length of the largest region in Boolean Matrix | A function to check if a given cell ( row , col ) can be included in DFS ; row number is in range , column number is in range and value is 1 and not yet visited ; A utility function to do DFS for a 2D boolean matrix . It only considers the 8 neighbours as adjacent vertices ; These arrays are used to get row and column numbers of 8 neighbours of a given cell ; Mark this cell as visited ; Recur for all connected neighbours ; increment region length by one ; The main function that returns largest length region of a given boolean 2D matrix ; Make a bool array to mark visited cells . Initially all cells are unvisited ; Initialize result as 0 and travesle through the all cells of given matrix ; If a cell with value 1 is not ; visited yet , then new region found ; maximum region ; Driver Code ; Function call
def isSafe ( M , row , col , visited ) : NEW_LINE INDENT global ROW , COL NEW_LINE return ( ( row >= 0 ) and ( row < ROW ) and ( col >= 0 ) and ( col < COL ) and ( M [ row ] [ col ] and not visited [ row ] [ col ] ) ) NEW_LINE DEDENT def DFS ( M , row , col , visited , count ) : NEW_LINE INDENT rowNbr = [ - 1 , - 1 , - 1 , 0 , 0 , 1 , 1 , 1 ] NEW_LINE colNbr = [ - 1 , 0 , 1 , - 1 , 1 , - 1 , 0 , 1 ] NEW_LINE visited [ row ] [ col ] = True NEW_LINE for k in range ( 8 ) : NEW_LINE INDENT if ( isSafe ( M , row + rowNbr [ k ] , col + colNbr [ k ] , visited ) ) : NEW_LINE INDENT count [ 0 ] += 1 NEW_LINE DFS ( M , row + rowNbr [ k ] , col + colNbr [ k ] , visited , count ) NEW_LINE DEDENT DEDENT DEDENT def largestRegion ( M ) : NEW_LINE INDENT global ROW , COL NEW_LINE visited = [ [ 0 ] * COL for i in range ( ROW ) ] NEW_LINE result = - 999999999999 NEW_LINE for i in range ( ROW ) : NEW_LINE INDENT for j in range ( COL ) : NEW_LINE INDENT if ( M [ i ] [ j ] and not visited [ i ] [ j ] ) : NEW_LINE INDENT count = [ 1 ] NEW_LINE DFS ( M , i , j , visited , count ) NEW_LINE result = max ( result , count [ 0 ] ) NEW_LINE DEDENT DEDENT DEDENT return result NEW_LINE DEDENT ROW = 4 NEW_LINE COL = 5 NEW_LINE M = [ [ 0 , 0 , 1 , 1 , 0 ] , [ 1 , 0 , 1 , 1 , 0 ] , [ 0 , 1 , 0 , 0 , 0 ] , [ 0 , 0 , 0 , 0 , 1 ] ] NEW_LINE print ( largestRegion ( M ) ) NEW_LINE