leedcode 1254. 统计封闭岛屿的数目

题目：

二维矩阵 grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，封闭岛是一个 完全 由1包围（左、上、右、下）的岛。

思路：封闭岛屿是由1完全包围的岛，也就是说，该岛屿不能在二维矩阵的边界处，这种情况排出后，统计剩余的封闭岛屿即可

广度优先遍历

代码如下：

class Solution {
    int[][] a = {{1,0},{-1,0},{0,1},{0,-1}};

    public int closedIsland(int[][] grid) {
        int nx = grid.length;
        int ny = grid[0].length;
        int num = 0;//用于记录封闭岛屿的数量

        for (int r = 0; r < nx ; r++) {

            for (int c = 0; c < ny; c++) {//依次对每个位置进行遍历

                if(grid[r][c] == 0) {

                    grid[r][c] = 1;
                    Queue<int[]> que = new ArrayDeque<int[]>();
                    que.add(new int[] {r,c});
                    boolean fal = true;//用于判断是否为封闭岛屿

                    while(!que.isEmpty()) {//将该岛屿扩展

                        int[] ret =que.poll();
                        int x = ret[0], y = ret[1];

                        if(x == 0 || y == 0 || x == nx - 1 || y == ny - 1) {
                          //如果该岛屿存在边界处，则不是封闭岛屿
                            fal = false;
                        }

                        for (int k = 0; k < 4; k++) {//对该点上下左右进行遍历

                            int dx = x + a[k][0], dy = y + a[k][1];

                            if (dx >= 0 && dx < nx && dy >= 0 && dy < ny && grid[dx][dy] == 0) {//判断是否进行扩展
                                que.add(new int[]{dx,dy});
                                grid[dx][dy] = 1;
                            }
                        }
                    }

                    if (fal) {//如果为封闭岛屿则num++
                        num++;
                    }
                }
            }
        }
        return num;
    }
}

深度优先遍历

代码如下：

class Solution {
    boolean fal;//用于判断是否为封闭岛屿
    int dx;
    int dy;

    public int closedIsland (int[][] grid) {
        dx = grid.length;
        dy = grid[0].length;
        int num = 0;

        for(int r = 0;r < dx;r++){

            for(int c = 0;c < dy;c++){

                if(grid[r][c] == 0){//统计个数
                    fal = true;
                    dfs(grid,r,c);

                    if(fal) {
                        num++;
                    }
                }
            }
        }
        return num;
    }

    public void dfs (int[][] grid,int row,int col) {

        if(row < 0 || row >= dx || col < 0 || col >= dy || grid[row][col] == 1) {
            return;
        }

        if (row == 0 || row == dx - 1 || col == 0 || col == dy - 1) {//判断岛屿处于边界情况
            fal = false;
        }

        grid[row][col] = 1;

        dfs(grid,row+1,col);

        dfs(grid,row-1,col);

        dfs(grid,row,col+1);

        dfs(grid,row,col-1);
    }
}