class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for(int i=0; i<grid.length; i++) {
            for(int j=0; j<grid[0].length; j++) {
                //一块联通区域只会被统计一次，因为一次完整的递归会将联通区域中所有1抹去
                if(grid[i][j] == '1') {
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
    /**
        深度优先搜索
    */
    void dfs(char [][]grid, int x, int y) {
        //到达网格边缘或水边，终止递归（剪枝）
        if(x<0 || y<0 || x>=grid.length || y>=grid[0].length || grid[x][y]=='0') {
            return;
        }
        //将岛屿的1抹去，避免重复搜索
        grid[x][y] = '0';
        dfs(grid, x-1, y);
        dfs(grid, x+1, y);
        dfs(grid, x, y-1);
        dfs(grid, x, y+1);
    }
}

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for(int i=0; i<grid.length; i++) {
            for(int j=0; j<grid[0].length; j++) {
                //一块联通区域只会被统计一次，因为一次完整的搜索会将联通区域中所有1抹去
                if(grid[i][j] == '1') {
                    bfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
    /**
        广度优先搜索
     */
    void bfs(char [][]grid, int i, int j) {
        Queue<int []> queue = new LinkedList<>();
        queue.add(new int []{i, j});
        while(!queue.isEmpty()){
            int []removeArray = queue.poll();
            int x = removeArray[0];
            int y = removeArray[1];
            if(x>=0 && y>=0 && x<grid.length && y<grid[0].length && grid[x][y]=='1') {
                //将岛屿上的1抹去，避免重复计算
                grid[x][y] = '0';
                queue.add(new int []{x-1, y});
                queue.add(new int []{x+1, y});
                queue.add(new int []{x, y-1});
                queue.add(new int []{x, y+1});
            }
        }
    }
}