Very easy DFS Solution


#1
int dfs(vector<vector<int>>& grid, int i, int j, int m, int n)
{
    if(i < 0 || j < 0 || i >= m || j >= n || grid[i][j] != 1)
            return 0;
    grid[i][j] = 2; //2 is to indicate that the curr_cell is visited
    return (1 + dfs(grid,i-1,j,m,n)
              + dfs(grid,i-1,j+1,m,n)    
              + dfs(grid,i,j+1,m,n)
              + dfs(grid,i+1,j+1,m,n)
              + dfs(grid,i+1,j,m,n) 
              + dfs(grid,i+1,j-1,m,n)
              + dfs(grid,i,j-1,m,n)
              + dfs(grid,i-1,j-1,m,n));
}
int Solution::solve(vector<vector<int>> &grid)
{
    int m = grid.size(), n = grid[0].size();
    int area = 0;
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (grid[i][j] == 1)
            {
                area = max(area, dfs(grid, i, j, m, n));
            }
        }
    }
    return area;
}

#2

Dont you think that changing the values in the input grid will affect the solution suppose some cells are part of two separate regions and the one with smaller area comes first, in that case you might change those common cells and when you compute for the solution during second region the answer will decrease because the common cells are changes to ‘2’ .


#3

No I don’t think so that it would have any effect on our answer as it isn’t possible for a cell to be part of two seperate regions as if it is the connecting cell between those two regions and its considered as a same region