# 934 Shortest Bridge

You are given an `n x n` binary matrix `grid` where `1` represents land and `0` represents water.

An island is a 4-directionally connected group of `1`'s not connected to any other `1`'s. There are exactly two islands in `grid`.

You may change `0`'s to `1`'s to connect the two islands to form one island.

Return the smallest number of `0`'s you must flip to connect the two islands.

Example 1:

``````Input: grid = [
[0,1],
[1,0]
]
Output: 1
``````

Example 2:

``````Input: grid = [
[0,1,0],
[0,0,0],
[0,0,1]
]
Output: 2
``````

Example 3:

``````Input: 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]
]
Output: 1
``````

Constraints:

• `n == grid.length == grid[i].length`
• `2 <= n <= 100`
• `grid[i][j]` is either `0` or `1`.
• There are exactly two islands in `grid`.
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 `````` ``````class Solution: def shortestBridge(self, grid: List[List[int]]) -> int: n = len(grid) DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)] def find_island() -> Tuple[int, int]: for i in range(n): for j in range(n): if grid[i][j] == 1: return i, j return -1, -1 def dfs(i: int, j: int, q: List[Tuple[int, int]]) -> None: grid[i][j] = -1 # add to q, used by BFS q.append((i, j)) for dx, dy in DIRS: x, y = i + dx, j + dy if 0 <= x < n and 0 <= y < n and grid[x][y] == 1: dfs(x, y, q) step = 0 q = [] ix, iy = find_island() dfs(ix, iy, q) # expand the found island using BFS while q: temp_q = [] for i, j in q: for dx, dy in DIRS: x, y = i + dx, j + dy if 0 <= x < n and 0 <= y < n: if grid[x][y] == 1: return step elif grid[x][y] == 0: grid[x][y] = -1 temp_q.append((x, y)) step += 1 q = temp_q return -1``````