[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. \

  1. Iterate over the input two-dimensional array if the current value is1Is a piece of land, and the land must belong to the island, so the number of updated islands +1.
  2. Change the current land to0And because the neighboring land belongs to the same island, the adjacent land is found and modified to0.
  3. After step 2, the number of each island can be obtained and the corresponding land can be modified as0, and the subsequent traversal reaches the value of1Must belong to a new island. Repeat Step 2.
  4. 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!