<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:
        # do dfs/bfs to find the islands and their areas
        # loop through all zeros, look at adjoining points, add up the max between two adjacent points (as long as they're not part of the same island) + 1 and the max of that should be our answer
        zeros = []
        n = len(grid)
        for i, row in enumerate(grid):
            for j,  value in enumerate(row):
                if value == 0:
                    zeros.append([i,j])
        if not zeros:
            return n*n
        areas = {}
        def bfs(coordinate, label):
            queue = deque()
            queue.append(coordinate)
            directions = [[0,1],[0,-1],[1,0],[-1,0]]
            while queue:
                x,y = queue.popleft()
                if grid[x][y] != 1:
                    continue
                grid[x][y] = label
                cur_area[0] += 1
                for direction in directions:
                    new_x, new_y = x + direction[0], y + direction[1]
                    if 0 <= new_x < n and 0 <= new_y < n and grid[new_x][new_y] == 1:
                        queue.append((new_x,new_y))
        label = -1
        for i, row in enumerate(grid):
            for j,  value in enumerate(row):
                if value == 1:
                    cur_area = [0]
                    bfs((i,j), label)
                    areas[label] = cur_area[0]
                    label -= 1
        directions = [[0,1],[0,-1],[1,0],[-1,0]]
        current_max = 0
        #print(grid)
        for x,y in zeros:
            seen_labels = set()
            neighboring_areas = []
            for direction in directions:
                new_x, new_y = x + direction[0], y + direction[1]
                if 0 <= new_x < n and 0 <= new_y < n and grid[new_x][new_y] != 0:
                    label = grid[new_x][new_y]
                    if label in seen_labels:
                        neighboring_areas.append(0)
                    else:
                        area = areas[label]
                        neighboring_areas.append(area)
                        seen_labels.add(label)
                else:
                    neighboring_areas.append(0)
            joined_area = sum(neighboring_areas) + 1
            current_max = max(current_max, joined_area)
        print(areas)
        return current_max

46768