Shortest Bridge

grid contains exactly two four-directionally connected islands of 1s. Return the minimum number of 0 cells that must be changed to 1 to connect the islands.

Function
shortestBridge(grid: int[][]) → int

Examples
Example 1
grid = [[0,1],[1,0]]
return = 1
Flipping either remaining zero joins the islands.

Constraints
2 <= grid.length, grid[0].length <= 100.
The grid contains exactly two islands.

Here's the trick. Step one: scan for the first 1 and DFS the whole island, marking every cell visited (flip to 2 or use a seen set) and pushing each cell into a queue. Step two: run BFS outward from that entire queue at once, level by level. Each level is one flipped 0. The first time you touch a 1 that isn't marked, return the level count. The pitfall is starting BFS from a single cell instead of the whole island, which gives a wrong, too-large answer. Another one is forgetting to mark visited zeros, so the queue blows up on a 100 by 100 grid. Check the four-direction bounds carefully. On the example [[0,1],[1,0]], island one is (0,1), BFS reaches a zero at level one, then hits the other island, so the answer is 1. If the live OA freezes you, StealthCoder is the hedge that hands you this structure.

Drill it cold or hedge it with StealthCoder. Either way, don't walk into the OA hoping you remember the trick.