Making A Large Island

https://leetcode.com/explore/challenge/card/august-leetcoding-challenge-2021/613/week-1-august-1st-august-7th/3835/

// mine.
// 368ms.
class Solution {
public:
    int largestIsland(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        
        int gr = 1;
        int count = 0;
        vector<vector<int>> v(n, vector<int>(m, 0));
        map<int, int> gr_count;
            
        
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (!grid[i][j]) continue;
                make(grid, v, gr_count, i, j, gr);
            }
        }
        
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j]) continue;
                
                int top = i > 0 ? v[i-1][j] : 0;
                int left = j > 0 ? v[i][j-1] : 0;
                int right = j < m-1 ? v[i][j+1] : 0;
                int bottom = i < n-1 ? v[i+1][j] : 0;
                
                int count = 1 + gr_count[top];
                if (top != left) count += gr_count[left];
                if (top != right && left != right) count += gr_count[right];
                if (top != bottom && left != bottom && right != bottom) count += gr_count[bottom];
                ans = max(ans, count);
            }
        }
        return ans ? ans : n*m;
    }
    
    void make(vector<vector<int>> &grid, vector<vector<int>> &v, map<int, int> &gr_count, int y, int x, int &gr) {
        if (grid[y][x] == 0) return;
        if (v[y][x]) return;
        
        int n = grid.size();
        int m = grid[0].size();
        int count = 0;
        
        queue<pair<int, int>> que;
        que.push({y, x});
        
        while (!que.empty()) {
            auto t = que.front();
            que.pop();
            
            if (t.first < 0 || t.first >= n || t.second < 0 || t.second >= m) continue;
            if (grid[t.first][t.second] == 0) continue;
            if (v[t.first][t.second]) continue;
            
            ++count;
            v[t.first][t.second] = gr;
            
            que.push({t.first - 1, t.second});
            que.push({t.first, t.second - 1});
            que.push({t.first + 1, t.second});
            que.push({t.first, t.second + 1 });
        }
        
        gr_count[gr++] = count;
    }
};

 

//180ms  - easy to understand - less obj construction/copy
class Solution {
public:
    int largestIsland(vector<vector<int>>& grid) {
        const int bias = 2;
        vector<int> counts;
        size_t s = grid.size();
        this->s = s;
        for (size_t i = 0; i < s; ++i) {
            for (size_t j = 0; j < s; ++j) {
                if (grid[i][j] == 1) {
                    int count = dfs(grid, i, j, counts.size() + bias);
                    counts.emplace_back(count);
                }
            }
        }

        if (counts.size() == 0) {
            return 1;
        }

        int largest = counts.front();
        for (size_t i = 0; i < s; ++i) {
            for (size_t j = 0; j < s; ++j) {
                if (grid[i][j] == 0) {
                    int top = -1;
                    int bottom = -1;
                    int left = -1;
                    int right = -1;

                    int candidate = 1;
                    if (j > 0) {
                        top = grid[i][j - 1] - bias;
                        if (top >= 0) {
                            candidate += counts[top];
                        }
                    }

                    if (i > 0) {
                        left = grid[i - 1][j] - bias;
                        if (left >= 0 && left != top) {
                            candidate += counts[left];
                        }
                    }

                    if (i + 1 < s) {
                        right = grid[i + 1][j] - bias;
                        if (right >= 0 && right != top && right != left) {
                            candidate += counts[right];
                        }
                    }

                    if (j + 1 < s) {
                        bottom = grid[i][j + 1] - bias;
                        if (bottom >= 0 && bottom != top && bottom != left && bottom != right) {
                            candidate += counts[bottom];
                        }
                    }

                    if (candidate > largest) {
                        largest = candidate;
                    }
                }
            }
        }

        return largest;
    }
    size_t s;
    int dfs(vector<vector<int>>& grid, int i, int j, int v) {
        grid[i][j] = v;
        int ret = 1;
        if (i > 0 && grid[i - 1][j] == 1) {
            ret += dfs(grid, i - 1, j, v);
        }
        if (i + 1 < s && grid[i + 1][j] == 1) {
            ret += dfs(grid, i + 1, j, v);
        }
        if (j > 0 && grid[i][j - 1] == 1) {
            ret += dfs(grid, i, j - 1, v);
        }
        if (j + 1 < s && grid[i][j + 1] == 1) {
            ret += dfs(grid, i, j + 1, v);
        }

        return ret;
    }
};