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.

Their thinking

This topic has seen quite many times on the Internet, the decision to take him down. First of all, I already know that this problem is done with the idea of backtracking, which is depth-first search

2. The base case of a grid is whether the length and width of the current traversed grid exceed the boundary. —- grid[r][c] = 2; // mark the grid as “traversed” 4, and compare with the character ‘1’

AC code

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

conclusion

The amount of code is not much, I am practicing the template of this recent backtracking, the code still needs to be hammered to feel.