Coding - Shortest Bridge

Problem Statement

You are given a binary grid with 0s (water) and 1s (land). An island is a group of connected 1s using four directions (up, down, left, and right). You need to return the minimum number of 0s that must be flipped to connect two islands (i.e., make the two islands have the same set of connected land).

Examples

Example 1: Input: grid = [ [0,1,0], [1,0,1], [0,0,0] ] Output: 1 Explanation: We need to flip at least one 0 to connect the two islands, and the flipped grid would look like this: [ [0,1,0], [1,1,1], [0,0,0] ]

Example 2: Input: grid = [ [1,1,0,0], [0,0,0,1], [0,1,0,0], [1,0,1,0] ] Output: 0 Explanation: We do not need to flip any 0s to connect the two islands because they are already connected.

Example 3: Input: grid = [ [1, 0, 0], [0, 0, 1], [1, 0, 1] ] Output: 2 Explanation: We need to flip two 0s to connect the islands, and the flipped grid would look like this: [ [1, 0, 0], [0, 1, 1], [1, 0, 1] ]

Constraints

• 1 <= grid.length <= 1000
• 1 <= grid[0].length <= 1000
• All islands have the same size and the above grid is non-empty and contains exactly two islands.

Hints

1. Use BFS to find the shortest path between the two islands.
2. Mark the visited nodes to avoid revisiting them.
3. Keep track of the distance from the starting point to each node.
4. Once you find a node that belongs to the second island, return the minimum distance found.