Joining two islands
Find the island you can already see, then grow outwards from all of it at once until you touch the other. About 14 minutes.
Two ideas, one after the other
A map has exactly two islands. You can turn water cells into land, and you want the fewest conversions so the islands become one. That is the shortest water crossing between them.
You already know both tools. First, flood fill to find every cell of one island and set those cells aside. Then start a ring search from all of those cells together. The rings spread through water, and the first ring that touches the other island tells you how many water cells were crossed.
- distance
- 0
Flood fill from the top-left land: this is the first island. Set its cells aside.
Why start the ring search from all cells of the first island, not just one cell?
- AThe bridge may start from any cell of the island, and all rings grow together
- BOne cell would be faster and just as correct
- CIt makes no difference
Show the answer
The bridge may start from any cell of the island, and all rings grow together. Starting from the whole island makes the first contact the true shortest crossing.
Shortest bridge
grid is a map where 1 is land and 0 is water. Land cells joined through shared edges (up, down, left or right) form an island, and the map contains exactly two islands. You may turn water cells into land. Return the smallest number of water cells you must turn into land so the two islands become one.
grid = [[1, 1, 0, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 1, 1], [0, 0, 0, 1, 1]] → 3
2 ≤ rows, columns ≤ 20 · exactly two islands