mediumGraphsPure DSA~35 min
Shortest Bridge Between Two Islands
A grid map has exactly two land masses separated by water. Build the shortest causeway — the fewest water cells to flip — connecting them.
Problem
Given an n x n binary grid with exactly two islands (4-directionally connected groups of 1s), return the smallest number of 0s that must be flipped to 1 to connect the two islands into one.
Input
An n x n binary grid containing exactly two islands.
Output
An integer: the minimum number of water cells to flip.
Constraints
- 2 <= n <= 100
- grid[i][j] is 0 or 1.
- Exactly two islands are present.
Examples
Example 1
Input
grid = [[0,1],[1,0]]
Output
1
Flipping one water cell connects the two diagonal land cells.
Example 2
Input
grid = [[0,1,0],[0,0,0],[0,0,1]]
Output
2
Two water flips bridge the corner islands.