Find length of the largest region in Boolean Matrix | Java program to find the length of the largest region in boolean 2D - 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 boolean array to mark visited cells . Initially all cells are unvisited ; Initialize result as 0 and traverse 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
import java . io . * ; import java . util . * ; class GFG { static int ROW , COL , count ; static boolean isSafe ( int [ ] [ ] M , int row , int col , boolean [ ] [ ] visited ) { return ( ( row >= 0 ) && ( row < ROW ) && ( col >= 0 ) && ( col < COL ) && ( M [ row ] [ col ] == 1 && ! visited [ row ] [ col ] ) ) ; } static void DFS ( int [ ] [ ] M , int row , int col , boolean [ ] [ ] visited ) { int [ ] rowNbr = { - 1 , - 1 , - 1 , 0 , 0 , 1 , 1 , 1 } ; int [ ] colNbr = { - 1 , 0 , 1 , - 1 , 1 , - 1 , 0 , 1 } ; visited [ row ] [ col ] = true ; for ( int k = 0 ; k < 8 ; k ++ ) { if ( isSafe ( M , row + rowNbr [ k ] , col + colNbr [ k ] , visited ) ) { count ++ ; DFS ( M , row + rowNbr [ k ] , col + colNbr [ k ] , visited ) ; } } } static int largestRegion ( int [ ] [ ] M ) { boolean [ ] [ ] visited = new boolean [ ROW ] [ COL ] ; int result = 0 ; for ( int i = 0 ; i < ROW ; i ++ ) { for ( int j = 0 ; j < COL ; j ++ ) { if ( M [ i ] [ j ] == 1 && ! visited [ i ] [ j ] ) { count = 1 ; DFS ( M , i , j , visited ) ; result = Math . max ( result , count ) ; } } } return result ; } public static void main ( String args [ ] ) { int M [ ] [ ] = { { 0 , 0 , 1 , 1 , 0 } , { 1 , 0 , 1 , 1 , 0 } , { 0 , 1 , 0 , 0 , 0 } , { 0 , 0 , 0 , 0 , 1 } } ; ROW = 4 ; COL = 5 ; System . out . println ( largestRegion ( M ) ) ; } }