934.Shortest Bridge
===
###### tags: `Medium`,`Array`,`Matrix`,`DFS`,`BFS`
[934. Shortest Bridge](https://leetcode.com/problems/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`.
### 解答
### Reference
[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)