0934. Shortest Bridge
Last updated
Was this helpful?
Last updated
Was this helpful?
Was this helpful?
https://leetcode.com/problems/shortest-bridge
In a given 2D binary array grid, there are two islands. (An island is a 4-directionally connected group of 1s not connected to any other 1s.)
Now, we may change 0s to 1s so as to connect the two islands together to form 1 island.
Return the smallest number of 0s that must be flipped. (It is guaranteed that the answer is at least 1.)
Example 1:
**Input:** grid = [[0,1],[1,0]]
**Output:** 1Example 2:
**Input:** grid = [[0,1,0],[0,0,0],[0,0,1]]
**Output:** 2Example 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:** 1Constraints:
2 <= grid.length == grid[0].length <= 100
grid[i][j] == 0 or grid[i][j] == 1