DIY: Shortest Bridge

Problem statement

You are given an n x n binary matrix grid containing 0s and 1s. Each cell in the grid represents either land or water. A cell with a value 1 represents land, while one with a value 0 represents water. A bunch of four-directionally adjacent cells with the value 1 constitutes an island.

There are exactly two islands in the grid.

You may change 0s to 1s to connect the two islands to form one island. Return the smallest number of 0s you must flip to connect the two islands.

You may assume all four edges of the grid are surrounded by water.

Constraints

You can assume the following constraints for this problem:

• n == grid.length == grid[i].length
• 2 <= n <= 100.
• grid[i][j] is either 0 or 1.
• There are exactly two islands in grid.

Input

The input will be an m x n grid, containing 0s and 1s. You can review the two examples below:

# Sample Input - 1
[
  [1, 0, 0] 
  [0, 0, 0]
  [0, 0, 1]
]

# Sample Input - 2
[
  [1, 0] 
  [0, 1]
]

Output

The output will be an integer value. The following are the example outputs for the above inputs:

# Sample Output - 1
3

# Sample Output - 2
1

In the first example, we can set the cells (0, 1), (0, 2), and (1, 2) to 1 to create the shortest bridge, which is 3. We can set some other cells, for example: (1, 0), (2, 0), and (2, 1) to 1 as well, but the shortest length would still be 3.

In the second example, we can set the top right, (0, 1), or the bottom left cell, (1, 0) to 1. Hence, the answer is 1.

Coding exercise

Implement the shortest_bridge(grid) function, where grid is the binary matrix containing 0s and 1s. There are exactly two islands in the grid. The function will return an integer value representing the minimum number of 0s to be flipped to join the two islands.