Let the flood report back
Make each flood return how many cells it covered, then keep the biggest. About 12 minutes.
A flood that counts
Last time the flood only marked cells. Now let it hand back a number. A call on water, off the map, or on a cell already flooded returns 0. A call on fresh land returns 1 for itself, plus whatever its four neighbours return.
So the first call on an island returns the island's whole area. It's like each cell asking its neighbours "how many did you cover?", adding itself, and passing the total up to whoever called it.
size = 1 size += flood(r + 1, c)
- best
- 3
- flood
- 3
The first flood starts at (0, 0) and returns 1 + the rest: it covers (0, 0), (0, 1) and (1, 1). Area 3.
Keep the largest
With a flood that returns an area, the rest is a small change to counting islands. Scan every cell. At each unflooded land square, start a flood and compare its answer with the best so far.
Start the best at 0, so a map with no land gives 0 rather than something odd. Overwriting visited land, as we do here, changes the map you were given. That is fine in a puzzle, but if the map is needed afterwards, keep a separate visited grid.
best = max(best, size)
A flood starts on a land cell and all four of its neighbours are water. What does that flood return?
- A1, for the cell itself
- B0, because nothing was found
- C4, one for each neighbour
Show the answer
1, for the cell itself. The starting cell counts for 1 and the four neighbours each add 0.
Biggest island
grid is a map where 1 is land and 0 is water. An island is a group of land cells joined through shared edges (up, down, left or right). Return the number of cells in the largest island, or 0 if there is no land.
grid = [[1, 1, 0, 1], [0, 1, 0, 1], [0, 0, 0, 1], [1, 0, 1, 1]] → 5
1 ≤ rows, columns ≤ 20 · each cell is 0 or 1