Shortest Bridge

You are given an n x n binary matrix grid where 1 represents land and 0 represents water. An island is defined as a group of 1s that are 4-directionally connected and not connected to any other 1s. The input grid is guaranteed to contain exactly two such islands.

Your task is to determine the minimum number of 0s (water cells) that need to be flipped to 1s (land cells) to connect these two islands into a single, contiguous island. Return this minimum number of flips.

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.

Similar LeetCode problem: Shortest Bridge