Count Islands in a Grid
Problem statement
You are given a map as a grid grid with m rows and n columns. Each cell is 1 for land or 0 for water.
Two land cells are connected when they share a side: one is directly above, below, left, or right of the other. Cells that touch only at a corner are not connected. An island is a group of land cells that are connected to each other, directly or through other land cells in the group, and not connected to any land outside the group. Cells outside the grid count as water.
Return the number of islands.
Function
countIslands(grid: int[][]) → intExamples
Example 1
grid = [[1,1,0,0,1],[0,1,0,1,1],[0,0,0,0,0],[1,0,1,1,0]]return = 4There are four islands: cells (0,0), (0,1), (1,1); cells (0,4), (1,3), (1,4); the single cell (3,0); and cells (3,2), (3,3). Here (r,c) means row r, column c, counting from 0.
Example 2
grid = [[1,0,0,1],[0,1,1,0],[1,0,0,1]]return = 5Cells (1,1) and (1,2) share a side, so they form one island. Each of the four corner cells touches that island only at a corner, and corners do not connect land, so each corner cell is its own island. The answer is 1 + 4 = 5.
Example 3
grid = [[1,1,1,1],[1,0,0,1],[1,1,1,1]]return = 1All ten land cells form one ring around two water cells. The ring is connected through shared sides, so there is 1 island.
Constraints
m == grid.lengthn == grid[i].lengthfor every row, so all rows have the same length.1 <= m, n <= 200- Each
grid[i][j]is0or1.