grid is a map where 1 is land and 0 is water, and it contains exactly two islands (groups of
land cells connected up, down, left or right). Engineers can turn water cells into land to build a
causeway. Return the smallest number of water cells that must be filled so that the two islands become
one connected island.
Examples
Input: grid = [[1, 0, 0],
[0, 0, 0],
[0, 0, 1]]
Output: 3
Explanation: for example fill (0,1), (0,2) and (1,2).
Input: grid = [[1, 0, 1]]
Output: 1
Input: grid = [[1, 1, 0, 0],
[1, 0, 0, 1],
[0, 0, 0, 1]]
Output: 2
Explanation: fill (0,2) and (0,3). No single water cell touches both islands.
Constraints
1 <= rows, cols <= 80; the grid contains exactly two islands.- Target
O(rows * cols)time.
Goals
- Label one island completely with a flood fill
- Grow a multi-source BFS outward from the whole island
- Convert the BFS distance into the number of cells to fill