“This is the 19th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”

Topic describes

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: 1

  • 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: 3

  • Tip:
  1. m == grid.length
  2. n == grid[i].length
  3. 1 <= m, n <= 300
  4. grid[i][j]The value of'0' 或 '1'

Subject analysis

If we want to know what counts as an island, the first is either a 1 inside and 0 around it, or a 1 at the edge of an array.

How do you determine what’s around the starting point of an array? We started off with DFS recursing in four directions, up, down, left, and right, and then recursing we all know that you have to have an exit condition or an end condition, and in this case, if the perimeter is 0, you don’t recurse anymore, you end up with that;

But if two numbers are close, we don’t need to go through them. When we do DFS, if we find this point, we set it to 0, because if we find this point, it’s on the island where we started, so DFS sets it to 0.

class Solution { public int numIslands(char[][] grid) { int num = 0; for(int i=0; i<grid.length; i++){ for(int j=0; j<grid[i].length; j++){ if(grid[i][j] == '1'){ dfs(i,j,grid); num++; } } } return num; } public void dfs(int i,int j,char[][] grid){ grid[i][j] = 0; if(i-1 >=0 && grid[i-1][j] == '1'){ dfs(i-1,j,grid); } if(i+1 <=grid.length-1 && grid[i+1][j] == '1'){ dfs(i+1,j,grid); } if(j-1 >=0 && grid[i][j-1] == '1'){ dfs(i,j-1,grid); } if(j+1 <=grid[i].length-1 && grid[i][j+1] == '1'){ dfs(i,j+1,grid); }}}Copy the code