【算法】Number of Closed Islands 统计封闭岛屿的数目-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法】Number of Closed Islands 统计封闭岛屿的数目。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Number of Closed Islands 统计封闭岛屿的数目

问题描述：

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

请返回封闭岛屿的数目。

行，列范围[1,100] ， $g r i d [i] [j]$ ==0OR1

分析

问题要求封闭island的数量，就是找出完全被1包围的0。

非常典型的矩阵遍历。
思路比较多

首先就是对每个0出现的位置开始 $BFS$ 或者 $D FS$ 遍历，把能达到的0全部找出来，这样就是一个 $i s l an d$ ，这个island不一定是封闭的，要么在遍历完成后，得到确切的结果， $i s l an d$ 是否封闭，要么在遍历时就保证该坐标所属的 $i s l an d$ 一定是封闭的。
其次，如果不对坐标记录，那么在遍历的过程中可能会遇到之前的坐标0，可以使用标记数组，也可以直接修改访问过的0.

所以不同的处理方式，导致的整体结构流程会有差异。但是时间复杂度上，基本是相同的。

可以把所有边界 $b o u n d a ry$ 上的 $0$ ，都进行标记为 $x, x! = 0∣∣1$ ，使用 $D FS$ 或者 $BFS$ 都可以。
到此，矩阵中剩余的0一定属于封闭island，然后依次遍历所有的坐标，到达一个0值坐标后，进行DFS或者BFS，为了将island进行标记，同时ans++。最终返回结果。

代码

int[][] dir = new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
    int rows,cols;
    int[][] g;
    public int closedIsland(int[][] grid) {
        rows = grid.length;
        cols = grid[0].length;
        g = grid;
        for(int i = 0;i<rows;i++){ 
            if(g[i][0]==0) color(i,0);            
            if(g[i][cols-1]==0) color(i,cols-1);
        }
        for(int i = 0;i<cols;i++){             
            if(g[0][i]==0) color(0,i);
            if(g[rows-1][i]==0) color(rows-1,i);
        }
        int ans =0;
        for(int i = 0;i<rows;i++){
            for(int j = 0;j<cols;j++){
                if(g[i][j]!=0) continue;
                color(i,j);
                ans++;
            }
        }
        return ans;    
    }

    public void color(int x,int y){
        Queue<int[]> queue = new LinkedList();
        queue.offer(new int[]{x,y});
        while(!queue.isEmpty()){
            int len = queue.size();
            for(int i = 0;i<len;i++){
                int[] cordi = queue.poll();
                g[cordi[0]][cordi[1]] = 2;// is visted
                for(int k = 0;k<4;k++){
                    int nx = cordi[0]+dir[k][0];    
                    int ny = cordi[1]+dir[k][1];    
                    if(nx<0||nx>=rows) continue;
                    if(ny<0||ny>=cols) continue;
                    if(g[nx][ny]!=0)continue;
                    queue.offer(new int[]{nx,ny});
                }
            }
        }
        return;
    }