1254. 统计封闭岛屿的数目

力扣题目链接

二维矩阵 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 <= grid.length, grid[0].length <= 100
• 0 <= grid[i][j] <=1

思路

和 1020. 飞地的数量 思路是一样的，代码也基本一样

class Solution {
private:
    int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1}; // 保存四个方向
    void dfs(vector<vector<int>>& grid, int x, int y) {
        grid[x][y] = 1;
        for (int i = 0; i < 4; i++) { // 向四个方向遍历
            int nextx = x + dir[i][0];
            int nexty = y + dir[i][1];
            // 超过边界
            if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;
            // 不符合条件，不继续遍历
            if (grid[nextx][nexty] == 1) continue;

            dfs (grid, nextx, nexty);
        }
        return;
    }

public:
    int closedIsland(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        // 从左侧边，和右侧边 向中间遍历
        for (int i = 0; i < n; i++) {
            if (grid[i][0] == 0) dfs(grid, i, 0);
            if (grid[i][m - 1] == 0) dfs(grid, i, m - 1);
        }
        // 从上边和下边 向中间遍历
        for (int j = 0; j < m; j++) {
            if (grid[0][j] == 0) dfs(grid, 0, j);
            if (grid[n - 1][j] == 0) dfs(grid, n - 1, j);
        }
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 0) {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }
};

其他语言版本

JavaScript:

/**
 * @param {number[][]} grid
 * @return {number}
 */
var closedIsland = function(grid) {
    let rows = grid.length;
    let cols = grid[0].length;
    // 存储四个方向
    let dir = [[-1, 0], [0, -1], [1, 0], [0, 1]];
    // 深度优先
    function dfs(x, y) {
        grid[x][y] = 1;
        // 向四个方向遍历
        for(let i = 0; i < 4; i++) {
            let nextX = x + dir[i][0];
            let nextY = y + dir[i][1];
            // 判断是否越界
            if (nextX < 0 || nextX >= rows || nextY < 0 || nextY >= cols) continue;
            // 不符合条件
            if (grid[nextX][nextY] === 1) continue;
            // 继续递归
            dfs(nextX, nextY);
        }
    }
    // 从边界岛屿开始
    // 从左侧和右侧出发
    for(let i = 0; i < rows; i++) {
        if (grid[i][0] === 0) dfs(i, 0);
        if (grid[i][cols - 1] === 0) dfs(i, cols - 1);
    }
    // 从上侧和下侧出发
    for(let j = 0; j < cols; j++) {
        if (grid[0][j] === 0) dfs(0, j);
        if (grid[rows - 1][j] === 0) dfs(rows - 1, j);
    }
    let count = 0;
    // 排除所有与边界相连的陆地之后
    // 依次遍历网格中的每个元素，如果遇到一个元素是陆地且状态是未访问，则遇到一个新的岛屿，将封闭岛屿的数目加 1
    // 并访问与当前陆地连接的所有陆地
    for(let i = 0; i < rows; i++) {
        for(let j = 0; j < cols; j++) {
            if (grid[i][j] === 0) {
                count++;
                dfs(i, j);
            }
        }
    }
    return count;
};