# MGLISD Editorial, ONCO2020

**URL:** <https://discuss.codechef.com/t/mglisd-editorial-onco2020/52480>\
**Category:** editorial\
**Tags:** depth-first-search, editorial, grid, onco2020, disjoint-set-union\
**Created:** [February 9, 2020, 7:20am UTC](https://discuss.codechef.com/t/mglisd-editorial-onco2020/52480 "2020-02-09T07:20:14Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![mynk322](https://discuss.codechef.com/user_avatar/discuss.codechef.com/mynk322/32/10570_2.png) [@mynk322](https://discuss.codechef.com/u/mynk322)\
**Post date:** [February 9, 2020, 7:20am UTC](https://discuss.codechef.com/t/mglisd-editorial-onco2020/52480/1 "2020-02-09T07:20:14Z")

</div>

PROBLEM LINK: [Link](https://www.codechef.com/ONCO2020/problems/MGLISD)

SETTER: [mynk322(Mayank Padia)](https://www.codechef.com/users/mynk322)

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.

```auto
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.

```auto
    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](https://www.codechef.com/viewsolution/29446975)