Find length of the largest region in Boolean Matrix | 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 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ROW  4 NEW_LINE #define COL  5 NEW_LINE int isSafe ( int M [ ] [ COL ] , int row , int col , bool visited [ ] [ COL ] ) { return ( row >= 0 ) && ( row < ROW ) && ( col >= 0 ) && ( col < COL ) && ( M [ row ] [ col ] && ! visited [ row ] [ col ] ) ; } void DFS ( int M [ ] [ COL ] , int row , int col , bool visited [ ] [ COL ] , int & count ) { static int rowNbr [ ] = { -1 , -1 , -1 , 0 , 0 , 1 , 1 , 1 } ; static 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 , count ) ; } } } int largestRegion ( int M [ ] [ COL ] ) { bool visited [ ROW ] [ COL ] ; memset ( visited , 0 , sizeof ( visited ) ) ; int result = INT_MIN ; for ( int i = 0 ; i < ROW ; ++ i ) { for ( int j = 0 ; j < COL ; ++ j ) { if ( M [ i ] [ j ] && ! visited [ i ] [ j ] ) { int count = 1 ; DFS ( M , i , j , visited , count ) ; result = max ( result , count ) ; } } } return result ; } int main ( ) { int M [ ] [ COL ] = { { 0 , 0 , 1 , 1 , 0 } , { 1 , 0 , 1 , 1 , 0 } , { 0 , 1 , 0 , 0 , 0 } , { 0 , 0 , 0 , 0 , 1 } } ; cout << largestRegion ( M ) ; return 0 ; }