<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:
    def largestIsland(self, grid: List[List[int]]) -> int:
        """
        
        run dfs on every one node get the maximum area 
        every region is different 
        find the max regions and if they can be connected 

        """
        n = len(grid)

        def neighbors(row,col,n=n):
            for nrow,ncol in ((row-1,col),(row+1,col),(row,col+1),(row,col-1)):
                if nrow>=0 and nrow<n and ncol>=0 and ncol<n and grid[nrow][ncol]==1:
                    yield nrow,ncol

        def dfs(row,col,region,regions):
            stack = []
            stack.append((row,col))
            visited = set()
            visited.add((row,col))
            while stack:
                row,col = stack.pop()
                regions[(row,col)] = region
                for nrow,ncol in neighbors(row,col):
                    if grid[nrow][ncol]==1:
                        if (nrow,ncol) not in visited:
                            visited.add((nrow,ncol))
                            stack.append((nrow,ncol))
                            

            for row,col in visited:
                areas[(row,col)] = len(visited)


        ocean = []
        regions = {}
        areas = {}
        region =0 
        for row in range(n):
            for col in range(n):
                if grid[row][col]==1 and (row,col) not in regions:
                    dfs(row,col,region,regions)
                    region+=1
                else:
                    ocean.append((row,col))

        if ocean==[]:
            return max(max(areas.values()),1)

        max_area = 1

        while ocean:
            row,col = ocean.pop()
            possible_regions = []
            possible_areas = [] 
            for nrow,ncol in neighbors(row,col):
                region = regions[(nrow,ncol)]

                if region not in possible_regions:
                    possible_regions.append(region)

                    possible_areas.append(areas[(nrow,ncol)])
            max_area = max(sum(possible_areas)+1,max_area)
        return min(max_area,n*n)
                    
                    

                



        


76693