Connected Cell in a Grid | Editorial by aksingh007

Use simple Depth-First Search (DFS)( more a floodfill Algorithm)  algorithm but modify it to assign a unique number to each cell identified in a connected component. Because the cells 
are originally numbered with either a  or a  but the only cells we care about visiting contain a , we just have to mark each cell we visit during our search with some 
number other than a  (e.g., , , etc.).

```
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    static int dfs(int arr[][],int i,int j,boolean visited[][],int tot,int n,int m){
        if(i<0 || j<0 || i>=n || j>=m)
            return tot;
        if(visited[i][j] || arr[i][j]==0)
            return tot;
       visited[i][j]=true;
       
        tot++;
        int t=0;
        //System.out.println(i+ " "+j+":"+tot);
        tot=dfs(arr,i+1,j,visited,tot,n,m);
        tot=dfs(arr,i,j+1,visited,tot,n,m);
        tot=dfs(arr,i-1,j,visited,tot,n,m);
        tot=dfs(arr,i,j-1,visited,tot,n,m);
        
        tot=dfs(arr,i+1,j+1,visited,tot,n,m);
        tot=dfs(arr,i+1,j-1,visited,tot,n,m);
        tot=dfs(arr,i-1,j-1,visited,tot,n,m);
        tot=dfs(arr,i-1,j+1,visited,tot,n,m);
        
        return (tot);
        }

public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int [][]arr=new int[n][m];
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                arr[i][j]=sc.nextInt();
        int ans=1;
        boolean visited[][]=new boolean[n][m];
        int tot=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                tot=0;
                int x=dfs(arr,i,j,visited,tot,n,m);
                //System.out.println(x);
                if(x>ans)
                    ans=x;
            }
        }
        System.out.println(ans);
        
    }
}
```

Connected Cell in a Grid | Editorial by aksingh007

Download submission

All caught up!

View submission

Is your resume even shortlisted?