<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:
    constexpr static int dx[4] = {-1, 1, 0, 0};
    constexpr static int dy[4] = {0, 0, -1, 1};
    
    // check for adjacent ones. 0 means it's not land, != 1 means it belongs to
    // another island.
    vector<std::pair<int, int>> checkAdjacent(vector<vector<int>>& grid, int x, int y) {
        vector<std::pair<int, int>> res;
        // check all 4 directions
        // up
        if (x - 1 >= 0 && grid[x - 1][y] == 1) {
            res.push_back({x - 1, y});
        }
        // down
        if (x + 1 < grid.size() && grid[x + 1][y] == 1) {
            res.push_back({x + 1, y});
        }
        // left
        if (y - 1 >= 0 && grid[x][y - 1] == 1) {
            res.push_back({x, y - 1});
        }
        // right
        if (y + 1 < grid[0].size() && grid[x][y + 1] == 1) {
            res.push_back({x, y + 1});
        }
        return res;
    }

    bool checkAdjacentForIsland(vector<vector<int>>& grid, int x, int y,
                                int color) {
        // check all 4 directions
        // up
        if (x - 1 >= 0 && grid[x - 1][y] == color) {
            return true;
        }
        // down
        if (x + 1 < grid.size() && grid[x + 1][y] == color) {
            return true;
        }
        // left
        if (y - 1 >= 0 && grid[x][y - 1] == color) {
            return true;
        }
        // right
        if (y + 1 < grid[0].size() && grid[x][y + 1] == color) {
            return true;
        }
        return false;
    }

    // find the entire island starting from point (x, y) via bfs.
    int find_island_size(vector<vector<int>>& grid, int x, int y, int color) {
        int i_size = 0;
        std::queue<std::pair<int, int>> q;
        q.push({x, y});
        grid[x][y] = color;
        while (!q.empty()) {
            std::pair<int, int> cur = q.front();
            q.pop();
            i_size++;
            // color the current tile with the current color.
            // grid[cur.first][cur.second] = color;
            // find all adjacent 1s.
            vector<std::pair<int, int>> adjacent_ones = checkAdjacent(grid, cur.first, cur.second);
            for (auto p : adjacent_ones) {
                grid[p.first][p.second] = color;
                q.push(p);
            }
        }
        return i_size;
    }
    int largestIsland(vector<vector<int>>& grid) {
        int next_color = 2;
        unordered_map<int, int> color_to_size;
        int n = grid.size();
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                // found unmarked island
                if (grid[i][j] == 1) {
                    color_to_size[next_color] =
                        find_island_size(grid, i, j, next_color);
                    next_color++;
                }
            }
        }

        int cur_max = 0;
        for (auto [k, v]: color_to_size) {
            cur_max = std::max(cur_max, v);
        }
        // iterate the grid again an go through the zeros, check adjacent tiles
        // for any colors.
        // for (int i = 0; i < grid.size(); ++i) {
        //     for (int j = 0; j < grid[0].size(); ++j) {
        //         if (grid[i][j] == 0) {
        //             int connected_size = 0;
        //             // check adjacent
        //             for (int color = 2; color <= next_color; ++color) {
        //                 if (checkAdjacentForIsland(grid, i, j, color)) {
        //                     connected_size += color_to_size[color];
        //                 }
        //             }
        //             cur_max = std::max(cur_max, connected_size + 1);
        //         }
        //     }
        // }
        // Second pass: check zeros
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) {
                    unordered_set<int> neighbor_colors;
                    int size = 1;
                    for (int k = 0; k < 4; ++k) {
                        int ni = i + dx[k], nj = j + dy[k];
                        if (ni >= 0 && ni < n && nj >= 0 && nj < n && grid[ni][nj] > 1) {
                            neighbor_colors.insert(grid[ni][nj]);
                        }
                    }
                    for (int color : neighbor_colors) {
                        size += color_to_size[color];
                    }
                    cur_max = max(cur_max, size);
                }
            }
        }


        return cur_max;
    }
};
206409