<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>

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring> // memset
using namespace std;

class Solution {
public:
    struct Point { int row, col; };
    struct Cell { Point pos; int area; };
    int ROW, COL;
    const Point reach[ 4 ] = { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } };
    bool visited[ 500 * 500 ];

    int dfs( vector< vector< int > > &grid, int r, int c, bool *visited, vector< Cell > &region, int index ) {
       if( visited[ COL * r + c ] ) 
            return 0;

        visited[ COL * r + c ] = true;

        int area = 1;
        for( auto a : reach ) {
            Point x = { r + a.row, c + a.col };
            if( x.row < 0 || x.row >= ROW || x.col < 0 || x.col >= COL )
                continue; 
            if( grid[ x.row ][ x.col ] == 1 && !visited[ COL * x.row + x.col ] ) {
                grid[ x.row ][ x.col ] = index;
                area += dfs( grid, x.row, x.col, visited, region, index );
            }
            
            if( grid[ x.row ][ x.col ] == 0 ) { //check if it reaches another '1'-cell
                for( auto b : reach ) {
                    Point y = { x.row + b.row, x.col + b.col };
                    if( y.row < 0 || y.row >= ROW || y.col < 0 || y.col >= COL )
                        continue;
                    if( grid[ y.row ][ y.col ] == 1 && !visited[ COL * y.row + y.col ] ) {
                        region.push_back( { x, 1 } );
                        visited[ COL * x.row + x.col ] = true;
                    }
                }                
            }
        }
        return area;
    }

    int largestIsland(vector<vector<int>>& grid ) {
        COL = grid[ 0 ].size();
        ROW = grid.size();

        memset( visited, false, ROW * COL );

        vector< vector< Cell > > all_regions;
        vector< Cell > region;
        vector< int > region_area;

        int area = 0, seq = 2;  // to mark every region, starting from 2
        for( int row = 0; row < ROW; ++row ) {
           for( int col = 0; col < COL; ++col ) {
                if( grid[ row ][ col ] == 1 && !visited[ COL * row + col ] ) {
                    region.clear();
                    region.push_back( { { -1, seq }, 0 } );

                    grid[ row ][ col ] = seq;
                    area = dfs( grid, row, col, visited, region, seq++ );
                    region[ 0 ].area = area;
                    all_regions.push_back( region );

                    region_area.push_back( area ); // element 0 is for region index '2'
                }
           }
        }

        int ans = 0;
        const int count = all_regions.size();
        for( int r = 0; r < count; ++r ) { //for each region:
            vector< Cell > &R = all_regions[ r ];  // get a region
            if( R.size() == 1 ) {
                R[ 0 ].area += 1;
                if( ans < R[ 0 ].area )
                    ans = R[ 0 ].area;
                continue;
            }
            area = 1;
            int near[ 3 ];
            int d = 0;
            for( int i = 1; i < R.size(); ++i ) {  // to check if this joint reach a region
                near[ 0 ] = 0; near[ 1 ] = 0; near[ 2 ] = 0;
                d = 0;
                Point bridge = R[ i ].pos;
           
                for( auto n: reach ) {
                    Point y = { bridge.row + n.row, bridge.col + n.col };
                    if( y.row < 0 || y.row >= ROW || y.col < 0 || y.col >= COL )
                        continue;
                    int index = grid[ y.row ][ y.col ];
                    if( index == 0 )
                        continue;
                    if( index != R[ 0 ].pos.col ) //connects to another region 
                        near[ d++ ] = index;
                }
                // near[] : 6 6 6
                if( near[ 0 ] == near[ 1 ] ) near[ 0 ] = 0;
                if( near[ 1 ] == near[ 2 ] ) near[ 1 ] = 0;
                if( near[ 0 ] == near[ 2 ] ) near[ 2 ] = 0;
                for( auto a: near ) {
                    if( a == 0 ) continue;
                    R[ i ].area += region_area[ a - 2 ];
                }
                if( R[ i ].area > area )
                    area = R[ i ].area;
            }
            area += R[ 0 ].area;
            if( area > ans )
                ans = area;
        } //end of for-each bridge

        if( ans > ROW * COL ) ans = ROW * COL;
        if( ans == 0 ) ans = 1;

        //cout << "Max area: " << ans << endl;

        return ans;

    }
};

71746