Loading...
Loading...
Loading...
For a geography project, Kiran has a satellite map of a lake. The map is a grid of r rows and c columns. Each cell is 1 for land or 0 for water.
Land cells that share a side (up, down, left or right) belong to the same island. Cells that only touch at a corner do not. Everything outside the map is water.
Print the number of islands.
1 or 0, with no spaces.1 or 0.Example 1
Input
4 5 11000 11000 00100 00011
Output
3
A 2 × 2 block on the top left, one cell in the middle and a pair on the bottom right.
Example 2
Input
3 3 000 000 000
Output
0
Only water, so there are no islands.
Try the problem first. Open one hint at a time.
Scan the map row by row. The first land cell of an island you have not seen yet starts a new island.
From that cell, visit every land cell joined to it through shared sides, and mark them all as seen.
A map can be 300 × 300. A method that calls itself once per cell can run out of stack on a large island, so use a queue.
Check that a neighbour is inside the grid before you read its value.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor