largestRegion.java

import java.util.*;
import java.lang.*;
import java.io.*;

class GFG {
    
    static boolean isSafe(int[][] mat, int i, int j, boolean[][] visited){
        
        return (i>=0) && (i<mat.length) &&
            (j >= 0) && (j<mat[0].length)&&
            (mat[i][j] == 1) && !visited[i][j];
        
    }
    
    static int DFS(int[][] mat, int i, int j, boolean[][] visited, int count){
        
         int rowNbr[] = {-1, -1, -1, 0, 0, 1, 1, 1};
         int colNbr[] = {-1, 0, 1, -1, 1, -1, 0, 1};
        
        visited[i][j] = true;
        
        //recurse for all neighboures...
        
        for(int k = 0;k<8;k++){
            
            if(isSafe(mat, i + rowNbr[k], j + colNbr[k], visited)){
                ++count;
                count = DFS(mat, i + rowNbr[k], j + colNbr[k], visited, count);
            }
            
        }
        return count;
        
    }
    
    static int largestRegion(int[][] mat, int n, int m){
        
        boolean visited[][] = new boolean[n][m];
        int result = Integer.MIN_VALUE;
        int count = 0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                
                if(!visited[i][j] && mat[i][j] == 1){
                    //new region found...
                    
                    count = 1;
                    count = DFS(mat, i, j, visited,count);
                    
                    result = Math.max(result, count);
                }
                
            }
        }
        return result;
    }
    
    public static void main (String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        while(t-->0){
            int n = in.nextInt(),m = in.nextInt();
            int mat[][] = new int[n][m];
            
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    mat[i][j] = in.nextInt();
                }
            }
            
            System.out.println(largestRegion(mat,n,m));
            
        }
    }
}