<p>You are given an <code>n x n</code> binary matrix <code>grid</code>. You are allowed to change <strong>at most one</strong> <code>0</code> to be <code>1</code>.</p>

<p>Return <em>the size of the largest <strong>island</strong> in</em> <code>grid</code> <em>after applying this operation</em>.</p>

<p>An <strong>island</strong> is a 4-directionally connected group of <code>1</code>s.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,0],[0,1]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> Change one 0 to 1 and connect two 1s, then we get an island with area = 3.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,1],[1,0]]
<strong>Output:</strong> 4
<strong>Explanation: </strong>Change the 0 to 1 and make the island bigger, only one island with area = 4.</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,1],[1,1]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> Can&#39;t change any 0 to 1, only one island with area = 4.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= n &lt;= 500</code></li>
	<li><code>grid[i][j]</code> is either <code>0</code> or <code>1</code>.</li>
</ul>

class Solution {
public:
    int largestIsland(const vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<int>> ids = vector<vector<int>>(n, vector<int>(n, -1));
        int ones = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ones += grid[i][j];
            }
        }
        if (ones == 0) {
            return 1;
        }
        if (ones >= n * n - 1) {
            return n * n;
        }
        map<int, int> sizes;
        set<pair<int, int>> visited;
        int id = 0;
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] != 1) {
                    ids[r][c] = id;
                    id++;
                    continue;
                }
                if (visited.find({r, c}) != visited.end()) {
                    continue;
                }
                sizes[id] = traverse(grid, ids, visited, r, c, id);
                id++;
            }
        }

        int ans = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ans = max(ans, sizes[ids[i][j]]);
                if (grid[i][j]) {
                    continue;
                }
                ans = max(ans, cmp(i, j, ids, sizes));
            }
        }
        return ans;
    }

    int cmp(
        int r,
        int c,
        const vector<vector<int>>& ids,
        const map<int, int> &sizes) {
            int ans = 1;
            int n = ids.size();
            const vector<int> delta = {0, 1, 0, -1, 0};
            unordered_set<int> s;
            for (int i = 0; i < 4; i++) {
                auto r1 = r + delta[i];
                auto c1 = c + delta[i + 1];
                if (r1 < 0 || r1 >= n || c1 < 0 || c1 >= n) {
                    continue;
                }
                s.insert(ids[r1][c1]);
            }
            ans = 1;
            for (const auto id : s) {
                if (sizes.find(id) == sizes.end()) {
                    continue;
                }
                ans += sizes.at(id);                
            }
            return ans;
    }

    int traverse(const vector<vector<int>> &grid, vector<vector<int>> &ids, set<pair<int, int>> &v, int r, int c, int id) const {
        int n = grid.size();
        const vector<int> delta = {0, 1, 0, -1, 0};
        int sum = 1;
        ids[r][c] = id;
        v.emplace(r, c);
        for (int i = 0; i < 4; i++) {
            auto row = r + delta[i];
            auto col = c + delta[i + 1];
            if (row < 0 || row >= n || col < 0 || col >= n || v.find({row, col}) != v.end() || grid[row][col] == 0) {
                continue;
            }
            sum += traverse(grid, ids, v, row, col, id);
        }
        return sum;
    }
};

298546