< Previous 　　　　　　　　　　　　　　　　 Next >

934. Shortest Bridge (Medium)

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

Related Topics

[Depth-First Search] [Breadth-First Search] [Array] [Matrix]