PROBLEM LINK: Link

SETTER: mynk322(Mayank Padia)

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