Causeway Network
Hard · minimum spanning tree
A map of a shallow lagoon is a rectangular grid of characters. "1" is land and "0" is water. An island is a group of land cells joined up, down, left or right. Land cells that only touch diagonally belong to different islands.
The council wants every island connected to every other, directly or through other islands, by causeways. A link between two islands is a chain of water cells, each joined to the next up, down, left or right, that starts next to one island and ends next to the other. All the cells of a chain are water, so a link never crosses a third island. Building a link means filling in each water cell of its chain, and costs one per cell.
Each link is built on its own and pays for all of its own cells, even if another link happens to use the same water cell.
Return the smallest total cost of a set of links that connects all the islands. If there is one island, or none, return 0.
Examples
Example 1
Input: grid = [["1", "0", "0", "1"]]
Output: 2
There are two islands with two water cells between them, so one link of cost 2 joins them.
Example 2
Input: grid = [["1", "0", "0", "0", "0", "0", "1"], ["0", "0", "0", "0", "0", "0", "0"], ["0", "0", "0", "1", "0", "0", "0"]]
Output: 8
The left island links to the middle one with 4 cells and the right island links to the middle one with 4 cells. Linking the left and right islands directly would cost 5.
Example 3
Input: grid = [["1", "1"], ["1", "0"]]
Output: 0
Only one island, so nothing needs to be built.
Constraints
- 1 <= rows, cols <= 60 and rows * cols <= 1000
- Every cell is "0" or "1".
- All rows have the same length.