Goal: Find the island you can already see, then grow outwards from all of it at once until you touch the other.
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.
Flood: to find one island completely.
Multi-source rings: from the whole island, through water.
1 is land, 0 is water. Two islands. Fewest water cells to flip to join them?
01234
0
1
1
0
0
0
1
1
0
0
0
0
2
0
0
0
1
1
3
0
0
0
1
1
- distance
- 0
Flood fill from the top-left land: this is the first island. Set its cells aside.
Move 1 of 4