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)