<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(vector<vector<int>>& grid) {
    int n = grid.size(), result = 1;
    vector<int> island_size {0};
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] > 0) {
          grid[i][j] = 0;
          vector<pair<int, int>> nodes;
          int front = 0;
          nodes.emplace_back(i, j);
          do {
            const auto [x, y] = nodes[front];
            if (x > 0 && grid[x - 1][y] > 0) {
              grid[x - 1][y] = 0;
              nodes.emplace_back(x - 1, y);
            }
            if (y > 0 && grid[x][y - 1] > 0) {
              grid[x][y - 1] = 0;
              nodes.emplace_back(x, y - 1);
            }
            if (x + 1 < n && grid[x + 1][y] > 0) {
              grid[x + 1][y] = 0;
              nodes.emplace_back(x + 1, y);
            }
            if (y + 1 < n && grid[x][y + 1] > 0) {
              grid[x][y + 1] = 0;
              nodes.emplace_back(x, y + 1);
            }
            ++front;
          } while (front < nodes.size());
          for (auto& k : nodes) {
            grid[k.first][k.second] = -island_size.size();
          }
          island_size.emplace_back(nodes.size());
        }
      }
    }
    for (int x = 0; x < n; ++x) {
      for (int y = 0; y < n; ++y) {
        int size = grid[x][y] == 0;
        vector<pair<int, int>> islands;
        if (x > 0) {
          islands.emplace_back(grid[x - 1][y], island_size[-grid[x - 1][y]]);
        }
        if (y > 0) {
          islands.emplace_back(grid[x][y - 1], island_size[-grid[x][y - 1]]);
        }
        if (x + 1 < n) {
          islands.emplace_back(grid[x + 1][y], island_size[-grid[x + 1][y]]);
        }
        if (y + 1 < n) {
          islands.emplace_back(grid[x][y + 1], island_size[-grid[x][y + 1]]);
        }
        sort(islands.begin(), islands.end());
        islands.erase(unique(islands.begin(), islands.end()), islands.end());
        for (auto [_, island] : islands) {
          size += island;
        }
        result = max(result, size);
      }
    }
    return result;
  }
};
266653