<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 m;
    int n;
    int getIdx(int r,int c){
        return r*n+c;
    }
    int labelIsland(vector<vector<int>>& grid, int R, int C, int label){
        unordered_set<int> visited;
        vector<pair<int,int>> diffs{{-1,0},{1,0},{0,-1},{0,1}};
        deque<pair<int,int>> dq{{R,C}};
        visited.insert(getIdx(R,C));
        while(!dq.empty()){
            auto [r,c]=dq.front();
            dq.pop_front();
            grid[r][c]=label;
            int nextR,nextC,nextIdx;
            for(auto [dr,dc]:diffs){
                nextR=r+dr;
                nextC=c+dc;
                nextIdx=getIdx(nextR,nextC);
                if(nextR<0||nextR>=m||nextC<0||nextC>=n||visited.count(nextIdx)||grid[nextR][nextC]!=1)continue;
                visited.insert(nextIdx);
                dq.push_back({nextR,nextC});
            }
        }
        return visited.size();
    }
    int largestIsland(vector<vector<int>>& grid) {
        m=grid.size();
        n=grid[0].size();
        int label=2;
        unordered_map<int,int> sizes;
        int best=0;
        for(int r=0;r<m;r++){
            for(int c=0;c<n;c++){
                if(grid[r][c]==1){
                    int sz=labelIsland(grid,r,c,label);
                    // cout<<"r:"<<r<<", c:"<<c<<", sz:"<<sz<<endl;
                    sizes[label]=sz;
                    label++;
                    best=max(best,sz);
                }
            }
        }
        
        for(int r=0;r<m;r++){
            for(int c=0;c<n;c++){
                if(grid[r][c]!=0)continue;
                unordered_set<int> used;
                int sz=0;
                if(r>0&&grid[r-1][c]!=0){
                    sz+=sizes[grid[r-1][c]];
                    used.insert(grid[r-1][c]);
                }
                if(r+1<m&&grid[r+1][c]!=0&&!used.count(grid[r+1][c])){
                    sz+=sizes[grid[r+1][c]];
                    used.insert(grid[r+1][c]);
                }
                if(c>0&&grid[r][c-1]!=0&&!used.count(grid[r][c-1])){
                    sz+=sizes[grid[r][c-1]];
                    used.insert(grid[r][c-1]);
                }
                if(c+1<n&&grid[r][c+1]!=0&&!used.count(grid[r][c+1])){
                    sz+=sizes[grid[r][c+1]];
                    used.insert(grid[r][c+1]);
                }
                best=max(best,sz+1);
            }
        }

        return best;
    }
};
227671