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


'''

nxn
can only change one 0

what is largest island?


- need to find the size of each island
- need to find the "1" that connects to create largest size
- need to be able to identify islands uniquely


O(m*n)

1. identify each island and size.
2. check if changing one creates diff

1. fill them with the unique id,
2. track map id->size

[1, 0]
[0, 1]
[1, 2]
[1, 2]
'''

mask = [1, 0, -1, 0, 1]
class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        ids = [[0 for _ in range(n)] for _ in range(m)]
        size = [1]

        def fillIsland(grid, i, j):
            print(f"i({i}), j({j})")
            cur_sum = 1
            for k in range(1, len(mask)):
                ik, jk = i + mask[k-1], j + mask[k]
                if ik < 0 or jk < 0 or ik >= m or jk >= m or ids[ik][jk] or not grid[ik][jk]:
                    continue
                ids[ik][jk] = len(size)
                cur_sum += fillIsland(grid, ik, jk)
            return cur_sum
        
        for i in range(0, m):
            for j in range(0, n):
                if grid[i][j] == 1 and not ids[i][j]:
                    ids[i][j] = len(size)
                    cur_size = fillIsland(grid, i, j)
                    size.append(cur_size)
        
        res = 0
        for i in range(0, m):
            for j in range(0, n):
                id_set = set([ids[i][j]])
                for k in range(1, len(mask)):
                    ik = i + mask[k - 1]
                    jk = j + mask[k]
                    if ik < 0 or ik >= m or jk < 0 or jk >= n:
                        continue
                    id_set.add(ids[ik][jk])
                cur_sum = 0
                for id in id_set:
                    cur_sum += size[id]
                res = max(res, cur_sum)
                

        return res
























27531