651. Count the Islands
A drone photographs a flooded river delta and sends back a rectangular map grid with R rows and C columns. Every cell is either '1' (dry ground) or '0' (water). Two dry cells belong to the same patch of ground when one can be reached from the other by repeatedly stepping up, down, left or right from a dry cell onto another dry cell. Diagonal steps do not connect cells.
Return how many separate patches of dry ground the map contains. A map without any dry cell has zero patches. Aim for O(R * C) time and O(R * C) extra space, and avoid deep recursion because one patch can cover the entire map.
Example 1
- Input:
- grid = [["1","1","0","0"],["1","0","0","1"],["0","0","1","1"]]
- Output:
- 2
- Explanation:
The three dry cells in the upper left form one patch and the three at the lower right form another, so the answer is 2.
Example 2
- Input:
- grid = [["1","0","1"],["0","1","0"],["1","0","1"]]
- Output:
- 5
- Explanation:
Diagonal neighbours do not connect, so each of the five dry cells is its own patch and the answer is 5.
Example 3
- Input:
- grid = [["0","0","0","0"],["0","0","0","0"]]
- Output:
- 0
- Explanation:
There is no dry cell at all, so the answer is 0.
Constraints
1 ≤ R, C ≤ 400
grid[i][j] is '0' or '1'
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(R * C)
- Space
- O(R * C)