[B] [C] [D]
Given a two-dimensional grid of ‘1’ (land) and ‘0’ (water), count the number of islands in the grid.
Islands are always surrounded by water, and each island can only be formed by connecting adjacent lands horizontally and/or vertically.
Furthermore, you can assume that all four sides of the grid are surrounded by water.
Example 1:
Input: the grid = [[" 1 ", "1", "1", "1", "0"], [" 1 ", "1", "0", "1", "0"], [" 1 ", "1", "0" and "0" and "0"], [" 0 "and" 0 ", "0" and "0", "0"]] output: 1Copy the code
Example 2:
Input: the grid = [[" 1 ", "1", "0" and "0" and "0"], [" 1 ", "1", "0" and "0" and "0"], [" 0 "and" 0 ", "1", "0" and "0"], [" 0 "and" 0 ", "0", "1", "1"]] output: 3Copy the code
Tip:
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j]
The value of'0'
或'1'
Their thinking
This is a connectivity problem. Since land is joined together to form islands, we can obtain the number of islands in the following way. \
- Iterate over the input two-dimensional array if the current value is
1
Is a piece of land, and the land must belong to the island, so the number of updated islands +1. - Change the current land to
0
And because the neighboring land belongs to the same island, the adjacent land is found and modified to0
. - After step 2, the number of each island can be obtained and the corresponding land can be modified as
0
, and the subsequent traversal reaches the value of1
Must belong to a new island. Repeat Step 2. - Finally, after iterating through the input array, I get the number of islands.
The demo
Code implementation
Var numIslands = function(grid) {const x = grid[0]. Length,y = grid.length; // let res = 0; // iterate over the input array for(let I = 0; i<y; i++){ for(let j = 0; j<x; If (grid[I][j]==='1'){if(grid[I][j]==='1'){res++; / handle/deal with the current land (I, j)}}} / / amend the current land to 0, and recursive processing adjacent land function handle (I, j) {if (I < 0 | | I > = y | | j < 0 | | j > = x | | grid [I] [j] = = = '0') return; grid[i][j] = '0'; handle(i-1,j) handle(i+1,j) handle(i,j-1) handle(i,j+1) } return res; };Copy the code
At this point we are done with Leetcode-200 – number of islands
If you have any questions or suggestions, please leave a comment!