Flood the island
Treat every cell of a map as a place with up to four neighbours, and count the separate islands. About 14 minutes.
Flooding one island
Stand on a land square and pour water. It spreads to every connected land square, and never to the sea. That is the same exploring idea as depth-first search, only the places are cells.
From a cell, first check that it is on the map and is land that hasn't been visited. Then mark it so it won't be visited again, and flood the four neighbours. A handy trick is to overwrite the visited land with a different number, so no separate record is needed.
if r < 0 or r >= rows or c < 0 or c >= cols:
return- islands
- 1
Scan from the top-left. Cell (0, 0) is land that hasn't been seen, so that is island number 1.
Count the floods
To count islands, walk across the whole map, one cell at a time. Every time you reach a land square that hasn't been flooded, you have found a new island. Count one and flood it completely, so that none of its squares can start another count.
The number of times you had to start a flood is the number of islands. Each island starts exactly one flood, however big or oddly shaped it is.
islands = 0 islands += 1 # one flood started
Two land squares touch only at a corner, one up-left of the other. In this puzzle, are they on the same island?
- ANo, only squares that share an edge are connected
- BYes, any touching squares are connected
- COnly if the squares around them are land
Show the answer
No, only squares that share an edge are connected. Neighbours are up, down, left and right. A diagonal touch doesn't join them.
Count the islands
grid is a map of rows and columns 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, not diagonally). Return how many islands the map has.
grid = [[1, 1, 0, 0], [1, 0, 0, 1], [0, 0, 1, 1], [1, 0, 0, 0]] → 3
1 ≤ rows, columns ≤ 20 · each cell is 0 or 1