<p>You are given an <code>n x n</code> binary matrix <code>grid</code> where <code>1</code> represents land and <code>0</code> represents water.</p>

<p>An <strong>island</strong> is a 4-directionally connected group of <code>1</code>&#39;s not connected to any other <code>1</code>&#39;s. There are <strong>exactly two islands</strong> in <code>grid</code>.</p>

<p>You may change <code>0</code>&#39;s to <code>1</code>&#39;s to connect the two islands to form <strong>one island</strong>.</p>

<p>Return <em>the smallest number of </em><code>0</code><em>&#39;s you must flip to connect the two islands</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> grid = [[0,1],[1,0]]
<strong>Output:</strong> 1
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> grid = [[0,1,0],[0,0,0],[0,0,1]]
<strong>Output:</strong> 2
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == grid.length == grid[i].length</code></li>
	<li><code>2 &lt;= n &lt;= 100</code></li>
	<li><code>grid[i][j]</code> is either <code>0</code> or <code>1</code>.</li>
	<li>There are exactly two islands in <code>grid</code>.</li>
</ul>

def get_neighbors(n: int, i: int, j: int) -> List[List[int]]:
    result = []
    if i > 0:
        result.append([i - 1, j])
    if i < n - 1:
        result.append([i + 1, j])
    if j > 0:
        result.append([i, j - 1])
    if j < n - 1:
        result.append([i, j + 1])
    return result

def get_islands(n: int, grid: List[List[int]]) -> Dict[tuple[int], int]:
    component_id = 0
    component_map = {}
    visited = set()
    for (i, j) in [(i, j) for i in range(n) for j in range(n)]:
        if grid[i][j] == 0:
            continue
        if (i, j) in visited:
            continue
        to_visit = [(i, j)]
        while len(to_visit) > 0:
            (ii, jj) = to_visit.pop()
            if grid[ii][jj] == 0:
                continue
            if (ii, jj) in visited:
                continue
            visited.add((ii, jj))
            component_map[(ii, jj)] = component_id
            for (new_i, new_j) in get_neighbors(n, ii, jj):
                to_visit.append((new_i, new_j))
        component_id += 1
    return component_map

class Solution:
    def shortestBridge(self, grid: List[List[int]]) -> int:
        n = len(grid)
        islands_map = get_islands(n, grid)
        
        current = [(i, j) for (i, j) in islands_map if islands_map[(i, j)] == 0]
        visited = set()
        current_step = 0

        while len(current) > 0:
            next_list = []
            for (current_i, current_j) in current:
                if (current_i, current_j) in visited:
                    continue
                if (current_i, current_j) in islands_map and islands_map[(current_i, current_j)] == 1:
                    return current_step - 1
                visited.add((current_i, current_j))
                next_list.extend(get_neighbors(n, current_i, current_j))
            current = next_list
            current_step += 1

        return -1
19100