1254. 统计封闭岛屿的数目

LC每日一题，参考1254. 统计封闭岛屿的数目 - 力扣（Leetcode）。

题目

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

请返回 封闭岛屿 的数目。

输入：grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
输出：2
解释：
灰色区域的岛屿是封闭岛屿，因为这座岛屿完全被水域包围（即被 1 区域包围）。

输入：grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
输出：1

解题思路

• 深度优先搜索：找里面的比较困难,可以考虑先找边界标记为1,剩下的0就是封闭的,遍历时每次碰到0把相连的0都赋值为1(dfs),防止重复统计。

深度优先搜索

class Solution {
    int[][] g;
    int m,n;
    public int closedIsland(int[][] grid) {
        g = grid;
        m = grid.length;
        n = grid[0].length;
        //直接找中间的比较困难 反过来找边缘0标记为2
        for(int i = 0; i < m; i++) {
            if(g[i][0] == 0)dfs(i,0);
            if(g[i][n-1] == 0) dfs(i,n-1);
        }
        for(int j = 0; j < n; j++) {
            if(g[0][j] == 0)dfs(0,j);
            if(g[m-1][j] == 0) dfs(m-1,j);
        }
        int ans = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(g[i][j] == 0){
                    ans ++;
                    dfs(i,j);
                }
            }
        }
        return ans;
    }

    int[][] dirs = {{1,0},{0,1},{-1,0},{0,-1}};
    //把相连的边缘0转化为1
    void dfs(int x,int y){
        g[x][y] = 1;
        //为0判断四个方向
        for(int[] dir : dirs){
            int x1 = x+dir[0],y1 = y+dir[1];
            if(x1 >= 0 && x1 < m && y1 >= 0 && y1 < n) {
                if(g[x1][y1] == 0) dfs(x1,y1);
            }
        }
    }
}

复杂度分析

• 时间复杂度：O(mn),m/n分别为数组行数/列数。
• 空间复杂度：O(mn),递归栈空间。

**