# MGLISD Editorial, ONCO2020

DIFFICULTY:
Easy-Medium

PREREQUISITES:
DFS,BFS.

EXPLANATION
We want the largest area of contiguous cells in the grid that are Water(’.’) and the cell is just beside a land(’#’) cell.
Now we need to find these cells in the grid.
We can create another grid that has 0 and 1. Where 1 denoting a SpecialWater cell and 0 denoting not.

``````5 5
#....      01000
.....      11000
.....      00111
...#.      00101
.....      00111
``````

After this, we just need to find the largest area of contiguous ‘1’.
For this, we can write a simple DFS function.

``````    void dfs(ll x,ll y){
vis[i][j]=1;
c++;
for (int i = x-1; i <=x+1; ++i){
for (int j = y-1; j <=y+1; ++j){
if(check(i,j)){
dfs(i,j);
}
}
}
}
// check function checks if that cell exists or not and is it visited before or not.
// c is the count of cells only via SpecialWater which are adjacent to each other.
``````

Now we just need to find the maximum sized component.

Time Complexity: O(N*M)

Space Complexity: O(N*M)

Problem Setter Code: Solution

1 Like