# LeetCode 934: Shortest Bridge

## Problem Restatement

We are given an `n x n` binary matrix `grid`.

Each cell is either:

```python
0
```

or:

```python
1
```

A `1` represents land.

A `0` represents water.

An island is a group of `1`s connected in four directions:

```text
up
down
left
right
```

The grid contains exactly two islands.

We may flip water cells from `0` to `1`.

Return the smallest number of water cells we must flip to connect the two islands into one island. The official statement defines the grid this way and asks for the minimum number of `0`s to flip.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An `n x n` binary matrix `grid` |
| Output | Minimum number of `0`s to flip |
| Land | `1` |
| Water | `0` |
| Movement | Four-directional only |
| Guarantee | There are exactly two islands |

Function shape:

```python
class Solution:
    def shortestBridge(self, grid: list[list[int]]) -> int:
        ...
```

## Examples

Example 1:

```python
grid = [
    [0, 1],
    [1, 0],
]
```

There are two diagonal islands.

Diagonal cells are not connected, because only four-directional movement counts.

Flip one water cell:

```text
[0, 1]      [1, 1]
[1, 0]  or  [1, 0]
```

The islands become connected.

Answer:

```python
1
```

Example 2:

```python
grid = [
    [0, 1, 0],
    [0, 0, 0],
    [0, 0, 1],
]
```

The shortest bridge needs two flips.

One path is:

```text
(0, 1) -> (1, 1) -> (2, 1) -> (2, 2)
```

The water cells flipped are:

```text
(1, 1), (2, 1)
```

Answer:

```python
2
```

Example 3:

```python
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],
]
```

The middle island is surrounded by water, and the outer ring is the other island.

Flip one adjacent water cell to connect them.

Answer:

```python
1
```

These examples match the standard examples for this problem.

## First Thought: Try Every Water Cell

One direct idea is to try flipping different sets of water cells until the islands connect.

But that quickly becomes too expensive.

There can be many water cells, and the number of possible sets is huge.

We need to view the problem as a shortest-distance problem on a grid.

## Key Insight

We can solve the problem in two phases.

First, find one island and mark every cell in it.

Second, expand outward from all cells of that island at the same time using BFS.

The first time BFS reaches the second island, the current BFS distance is the minimum number of water cells we needed to flip.

This works because BFS explores cells in increasing distance order.

Since every water flip has the same cost, BFS gives the shortest bridge.

## Algorithm

Use DFS to find and mark the first island.

While marking it, push all of its cells into a queue.

Then run multi-source BFS from that queue.

At each BFS layer:

1. Expand from all current cells.
2. If a neighbor is water, mark it visited and add it to the queue.
3. If a neighbor is land from the second island, return the current number of flips.

We can mark visited cells directly in `grid` by changing the first island and visited water cells to `2`.

## Walkthrough

Use:

```python
grid = [
    [0, 1, 0],
    [0, 0, 0],
    [0, 0, 1],
]
```

First island:

```text
(0, 1)
```

Mark it as `2` and put it in the queue.

Initial queue:

```python
[(0, 1)]
```

Start BFS with:

```python
flips = 0
```

Layer `0` expands from `(0, 1)`.

It reaches water cells:

```text
(0, 0), (0, 2), (1, 1)
```

These would require `1` flip.

Next layer:

```python
flips = 1
```

Expand from those water cells.

From `(1, 1)`, we can reach:

```text
(2, 1)
```

That is another water cell.

Next layer:

```python
flips = 2
```

Expand from `(2, 1)`.

It touches the second island at:

```text
(2, 2)
```

So the answer is:

```python
2
```

## Correctness

The DFS phase finds one land cell and marks every land cell connected to it by four-directional movement. Therefore, it marks exactly one of the two islands.

All cells of the first island are inserted into the BFS queue. So the BFS starts from every possible bridge starting point on that island, not just one cell.

During BFS, each layer corresponds to flipping one more water cell. Cells reached at distance `d` are exactly the water cells that can be connected to the first island by flipping `d` water cells.

BFS explores grid cells in increasing distance order. Therefore, the first time it touches a land cell that still has value `1`, that land cell belongs to the second island, and the number of layers already expanded is the smallest possible number of water cells needed to connect the islands.

No shorter bridge can exist, because BFS would have reached the second island at an earlier layer.

So the returned value is the minimum number of flips.

## Complexity

Let:

```python
n = len(grid)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^2)` | Each cell is visited at most once |
| Space | `O(n^2)` | The BFS queue may store many cells |

## Implementation

```python
from collections import deque

class Solution:
    def shortestBridge(self, grid: list[list[int]]) -> int:
        n = len(grid)
        queue = deque()
        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        def dfs(row: int, col: int) -> None:
            if row < 0 or row >= n or col < 0 or col >= n:
                return

            if grid[row][col] != 1:
                return

            grid[row][col] = 2
            queue.append((row, col))

            for dr, dc in dirs:
                dfs(row + dr, col + dc)

        found = False

        for row in range(n):
            if found:
                break

            for col in range(n):
                if grid[row][col] == 1:
                    dfs(row, col)
                    found = True
                    break

        flips = 0

        while queue:
            for _ in range(len(queue)):
                row, col = queue.popleft()

                for dr, dc in dirs:
                    nr = row + dr
                    nc = col + dc

                    if nr < 0 or nr >= n or nc < 0 or nc >= n:
                        continue

                    if grid[nr][nc] == 1:
                        return flips

                    if grid[nr][nc] == 0:
                        grid[nr][nc] = 2
                        queue.append((nr, nc))

            flips += 1

        return -1
```

## Code Explanation

We use a queue for BFS:

```python
queue = deque()
```

The four valid movement directions are:

```python
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
```

The DFS marks the first island:

```python
grid[row][col] = 2
queue.append((row, col))
```

Marking the cell as `2` means it has already been visited.

Adding it to the queue means BFS can later expand from every cell of the first island.

After the first island is marked, BFS begins:

```python
flips = 0
```

For each BFS layer, we process the current queue size:

```python
for _ in range(len(queue)):
```

If we reach a cell with value `1`, it must belong to the second island:

```python
if grid[nr][nc] == 1:
    return flips
```

If we reach water, we mark it and add it to the queue:

```python
if grid[nr][nc] == 0:
    grid[nr][nc] = 2
    queue.append((nr, nc))
```

After each layer, we increase the number of flips:

```python
flips += 1
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.shortestBridge([
        [0, 1],
        [1, 0],
    ]) == 1

    assert s.shortestBridge([
        [0, 1, 0],
        [0, 0, 0],
        [0, 0, 1],
    ]) == 2

    assert s.shortestBridge([
        [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],
    ]) == 1

    assert s.shortestBridge([
        [1, 0, 0],
        [0, 0, 0],
        [0, 0, 1],
    ]) == 3

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[[0,1],[1,0]]` | Diagonal islands need one flip |
| `3 x 3` separated corners | Needs two flips |
| Ring island and center island | One flip connects them |
| Opposite corners in `3 x 3` | Longer bridge |