1. subject

Here you are ‘1’（ land ） and ‘0’（ water ） A two-dimensional mesh of , Please calculate the number of islands in the grid .
Islands are always surrounded by water , And each island can only be combined by horizontal direction / Or a vertical connection between adjacent lands .
Besides , You can Assume that all four edges of the mesh are surrounded by water .

Example 1：

 Input ：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
 Output ：1

Example 2：

 Input ：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
 Output ：3

Tips ：
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] The value of is ‘0’ or ‘1’

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/number-of-islands

2. Ideas

（1）DFS
Train of thought reference Kill all the islands in a second .

3. Code implementation （Java）

// Ideas 1————DFS
class Solution {
    
    public int numIslands(char[][] grid) {
    
        //res Save the number of Islands , The initial value is  0
        int res = 0;
        int m = grid.length;
        int n = grid[0].length;
        // Traverse grid
        for (int i = 0; i < m; i++) {
    
            for (int j = 0; j < n; j++) {
    
                if (grid[i][j] == '1') {
    
                    // Find an island 
                    res++;
                    // Use DFS Submerge the island ( Including the adjacent land up, down, left and right )
                    dfs(grid, i, j);
                }
            }
        }
        return res;
    }

    public void dfs(char[][] grid, int i, int j) {
    
        int m = grid.length;
        int n = grid[0].length;
        // Judge boundary condition 
        if (i < 0 || j < 0 || i >= m || j >= n) {
    
            return;
        }
        if (grid[i][j] == '0') {
    
            // The current position is already sea water , Then return directly 
            return;
        }
        // Change the current position to sea water , Equivalent to using an array visited Record the traversed nodes 
        grid[i][j] = '0';
        // At the same time, it also submerges the land up, down, left and right 
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
    }
}