557. Shortest Bridge
You receive an n × n grid grid of 0s and 1s, where 1 is land and 0 is water. Land cells that share an edge (up/down/left/right) belong to the same island, and the grid contains exactly two islands.
You may build a bridge by flipping water cells into land. Return the minimum number of 0s you must change to 1 so that the two islands merge into a single connected island.
Diagonal contact does not connect land — a bridge must be built through edge-adjacent cells.
Example 1:
Input: grid = [[0, 1, 0], [0, 0, 0], [0, 0, 1]]
Output: 2
Explanation: The islands are the single cells at row 0 col 1 and row 2 col 2. Flipping the two water cells between them — for instance (1,1) and (1,2) — links them; no single flip can.
Example 2:
Input: grid = [[1, 0], [0, 1]]
Output: 1
Explanation: The two corner cells only touch diagonally, which doesn't count. Flipping either water cell joins them.
Constraints:
- 2 ≤ n ≤ 100
- grid[i][j] is 0 or 1
- The grid contains exactly two islands.
Hints:
Two phases. Phase one: tell the islands apart — a flood fill (DFS/BFS) from any land cell marks one island completely. What is phase two now asking for?
Phase two is a shortest-path search through water. Seed a BFS with every cell of the marked island at distance 0 and expand only through water, one flip per layer. The first time a neighbor turns out to be the other island's land, the current distance is the answer — BFS reaches it along a fewest-flips route first.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: grid = [[0, 1, 0], [0, 0, 0], [0, 0, 1]]
Expected output: 2