[数据结构与算法]岛屿的数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/queue-stack/kbcqv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
代码一
思路，DFS。
遍历数组，每当遇到‘1’，就将上下左右的‘1’置零，并且递归这个过程直到出界，在递归的时候，将连在一起的岛屿面积不断缩小，最终岛屿的数量就是我们进行深度优先搜索的次数。这是评论区大牛的方法，我只是把自己的理解写出来

class Solution {
    public int numIslands(char[][] grid) {
        if(grid==null||grid.length==0){
            return 0;
        }
        int res = 0;
        for(int i = 0;i<grid.length;i++){
            for(int j = 0;j<grid[0].length;j++){
             //只有当前格子是1才开始计算
                if(grid[i][j]=='1'){
                //如果当前格子是1，岛屿的数量加1
                    res++;
                 //然后通过dfs把当前格子的上下左右4
                //个位置为1的都要置为0，因为他们是连着
                //一起的算一个岛屿
                    dfs(grid,i,j);
                }
            }
        }
        return res;
    }
    public void dfs(char[][] grid,int i ,int j){
        if(i<0||i>=grid.length||j<0||j>=grid[0].length||grid[i][j]=='0'){
            return;
        }
        grid[i][j] = '0';
        dfs(grid,i-1,j);
        dfs(grid,i+1,j);
        dfs(grid,i,j-1);
        dfs(grid,i,j+1);
    }
}

代码二
BFS

class Solution {
    public int numIslands(char[][] grid) {
        if(grid==null||grid.length==0){
            return 0;
        }
        int res = 0;
        for(int i = 0;i<grid.length;i++){
            for(int j = 0;j<grid[0].length;j++){
                if(grid[i][j]=='1'){
                    res++;
                    bfs(grid,i,j);
                }
            }
        }
        return res;
    }
    public void bfs(char[][] grid,int i ,int j){
        grid[i][j] = '0';
        int n = grid.length;
        int m = grid[0].length;
        Queue<Integer> queue = new LinkedList<>();
        int code = i*m + j;
        queue.add(code);
        while(!queue.isEmpty()){
            code = queue.poll();
            int x = code/m;
            int y = code%m;
            if(x>0&&grid[x-1][y]=='1'){
                grid[x-1][y] = '0';
                queue.add((x-1)*m+y);
            }
            if(x<n-1&&grid[x+1][y]=='1'){
                grid[x+1][y] = '0';
                queue.add((x+1)*m+y);
            }
            if(y>0&&grid[x][y-1]=='1'){
                grid[x][y-1] = '0';
                queue.add(x*m+y-1);
            }
            if(y<m-1&&grid[x][y+1]=='1'){
                grid[x][y+1] = '0';
                queue.add(x*m+y+1);
            }
        }
    }
}