MGLISD Editorial, ONCO2020

editorial
, , , ,
1

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

1 Like