Count Islands
You are given a grid grid of numbers. Each cell is either 1 (land) or 0 (water). The values are numbers, not strings.
Two land cells are connected if they are next to each other in any of the 8 directions: up, down, left, right, and the 4 diagonals. An island is a group of land cells that are all connected to each other, directly or through other land cells, and that is not connected to any other land cell.
Return the number of islands in the grid.
Note
Land cells that touch only at a corner are part of the same island.
Hint: go through every cell. When you find land that you have not visited yet, you have found a new island. Visit all of its land with a depth-first or breadth-first search, so you do not count it again.
Examples
Example 1
- Input:
- [[1,1,0,0,0],[0,1,0,0,1],[1,0,0,1,1],[0,0,0,0,0],[1,0,1,0,1]]
- Output:
- 5
The island in the top left has the cells (0,0), (0,1), (1,1) and (2,0); (2,0) joins through a diagonal. The cells (1,4), (2,3) and (2,4) form a second island. The three single cells in the last row are three more islands. Total: 5.
Example 2
- Input:
- [[1,0,1],[0,1,0],[1,0,1]]
- Output:
- 1
Every corner cell touches the center cell through a diagonal, so all five land cells form one island.
Example 3
- Input:
- [[0,0],[0,0]]
- Output:
- 0
There is no land, so there are no islands.
Constraints
1 <= grid.length <= 121 <= grid[i].length <= 12, and every row has the same length.grid[i][j]is0or1.
Run checks your code against the 3 examples. Submit checks it against all 203 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.