# 0934. Shortest Bridge

<https://leetcode.com/problems/shortest-bridge>

## Description

In a given 2D binary array `grid`, there are two islands.  (An island is a 4-directionally connected group of `1`s not connected to any other 1s.)

Now, we may change `0`s to `1`s so as to connect the two islands together to form 1 island.

Return the smallest number of `0`s that must be flipped.  (It is guaranteed that the answer is at least 1.)

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

* `2 <= grid.length == grid[0].length <= 100`
* `grid[i][j] == 0` or `grid[i][j] == 1`

## ac

```java
```