解法一：深度优先搜索

• 我们可以将二维网格看成一个无向图，竖直或水平相邻的 1 之间有边相连。
• 为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为1，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。
• 最终岛屿的数量就是我们进行深度优先搜索的次数。

class Solution {
    public int numIslands(char[][] grid) {
        if(grid==null || grid.length==0){
            return 0;
        }
        int n = grid.length;
        int m = grid[0].length;
        int sum = 0;

        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(grid[i][j]=='1'){
                    sum++;
                    dfs(grid, i, j);
                }
            }
        }

        return sum;
    }

    
    public void dfs(char[][] grid, int i, int j){
        int n = grid.length;
        int m = grid[0].length;

        if(i<0 || j<0 || i>=n || j>=m || grid[i][j]=='0'){
            return;
        }

        // 重置+遍历
        grid[i][j]='0';  //grid[i][j]=0;
        dfs(grid, i-1, j);
        dfs(grid, i+1, j);
        dfs(grid, i, j-1);
        dfs(grid, i, j+1);
    }
}

注意：

• 这里的数组是char数组，要用‘0’和‘1’来判断，而不是0和1。例如：grid[i][j]=0 => × grid[i][j]='0' => √
• 在递归函数里面，如果grid[i][j]=='0'则直接返回，否则重置后继续递归