Shortest Bridge

You are given a binary grid containing exactly two islands, where 1 is land and 0 is water. You must return the minimum number of 0s that must be flipped to connect the two islands.

Problem Statement

You are given a 2D binary grid grid representing land (0) and water (1). An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You can assume all four edges of the grid are all water.

Find an island of land and return the minimum number of cells to flip to make the island connected to the opposite corner of the grid (i.e., to connect two corners of the grid).

You are allowed to flip any water cell (1) to land (0). You cannot flip a land cell (0) to water (1). To connect the island to the opposite corner of the grid, you must find an island of land then flip the minimum number of water cells to connect the island to that corner.

Constraints

• 1 <= grid.length == grid[0].length <= 200
• 0 <= grid[i][j] <= 1

Examples

Example 1

Input: grid = [ [0,1,0], [0,0,0], [0,0,1] ]

Output: 2

Explanation: We need to flip the cells at (1,1) and (0,2) to connect two corners of the grid.

Example 2

Input: grid = [ [1,0,0], [0,0,0], [1,0,1] ]

Output: 6

Explanation: An island of land is formed by the 0s at (0,0), (1,1), and (2,2). We need to flip the water cells at (0,1), (0,2), (1,0), (1,2), (2,0), and (2,1) to connect the island to the corner at (2,2).

Example 3

Input: grid = [ [0,0,0], [0,1,0], [0,0,0] ]

Output: 0

Explanation: The island is already connected to the corner at (2,2).

Hints

• Use breadth-first search (BFS) to find the shortest path between the two islands.