统计封闭岛屿的数目

1254. 统计封闭岛屿的数目

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

请返回 封闭岛屿 的数目。

示例 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 区域包围）。

示例 2：

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

示例 3：

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

提示：

1 <= grid.length, grid[0].length <= 100
0 <= grid[i][j] <=1

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int closedIsland(vector<vector<int>>& grid) { } };

python3 解法, 执行用时: 72 ms, 内存消耗: 16.7 MB, 提交时间: 2023-06-18 09:37:42

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        def dfs(x: int, y: int) -> None:
            if x == 0 or x == m - 1 or y == 0 or y == n - 1:  # 边界
                nonlocal closed
                closed = False  # 不是封闭岛屿
            grid[x][y] = 1  # 标记 (x,y) 被访问，避免重复访问
            # 访问四方向的 0
            for i, j in (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1):
                if 0 <= i < m and 0 <= j < n and grid[i][j] == 0:
                    dfs(i, j)

        ans = 0
        for i in range(1, m - 1):
            for j in range(1, n - 1):
                if grid[i][j] == 0:  # 从没有访问过的 0 出发
                    closed = True
                    dfs(i, j)
                    ans += closed
        return ans

java 解法, 执行用时: 1 ms, 内存消耗: 41.7 MB, 提交时间: 2023-06-18 09:37:14

class Solution {
    private boolean closed;

    public int closedIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length, ans = 0;
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (grid[i][j] == 0) { // 从没有访问过的 0 出发
                    closed = true;
                    dfs(grid, i, j);
                    if (closed) ans++;
                }
            }
        }
        return ans;
    }

    private void dfs(int[][] grid, int x, int y) {
        if (x == 0 || x == grid.length - 1 || y == 0 || y == grid[x].length - 1) {
            if (grid[x][y] == 0) closed = false; // 到达边界
            return;
        }
        if (grid[x][y] != 0) return;
        grid[x][y] = 1; // 标记 (x,y) 被访问，避免重复访问
        dfs(grid, x - 1, y);
        dfs(grid, x + 1, y);
        dfs(grid, x, y - 1);
        dfs(grid, x, y + 1);
    }
}

golang 解法, 执行用时: 8 ms, 内存消耗: 4.6 MB, 提交时间: 2023-06-18 09:36:52

func closedIsland(grid [][]int) (ans int) {
    m, n := len(grid), len(grid[0])
    var closed bool
    var dfs func(int, int)
    dfs = func(x, y int) {
        if x == 0 || x == m-1 || y == 0 || y == n-1 {
            if grid[x][y] == 0 { // 到达边界
                closed = false
            }
            return
        }
        if grid[x][y] != 0 {
            return
        }
        grid[x][y] = 1 // 标记 (x,y) 被访问，避免重复访问
        dfs(x-1, y)
        dfs(x+1, y)
        dfs(x, y-1)
        dfs(x, y+1)
    }

    for i := 1; i < m-1; i++ {
        for j := 1; j < n-1; j++ {
            if grid[i][j] == 0 { // 从没有访问过的 0 出发
                closed = true
                dfs(i, j)
                if closed {
                    ans++
                }
            }
        }
    }
    return
}

golang 解法, 执行用时: 8 ms, 内存消耗: 4.6 MB, 提交时间: 2023-06-18 09:36:26

func closedIsland(grid [][]int) (ans int) {
    m, n := len(grid), len(grid[0])
    var dfs func(int, int)
    dfs = func(x, y int) {
        if x < 0 || x >= m || y < 0 || y >= n || grid[x][y] != 0 {
            return
        }
        grid[x][y] = 1 // 标记 (x,y) 被访问，避免重复访问
        dfs(x-1, y)
        dfs(x+1, y)
        dfs(x, y-1)
        dfs(x, y+1)
    }

    for i := 0; i < m; i++ {
        // 如果是第一行和最后一行，访问所有格子
        // 如果不是，只访问第一列和最后一列的格子
        step := 1
        if 0 < i && i < m-1 {
            step = n - 1
        }
        for j := 0; j < n; j += step {
            dfs(i, j)
        }
    }

    for i := 1; i < m-1; i++ {
        for j := 1; j < n-1; j++ {
            if grid[i][j] == 0 { // 从没有访问过的 0 出发
                ans++ // 一定是封闭岛屿
                dfs(i, j)
            }
        }
    }
    return
}

java 解法, 执行用时: 1 ms, 内存消耗: 42.1 MB, 提交时间: 2023-06-18 09:36:08

class Solution {
    public int closedIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for (int i = 0; i < m; i++) {
            // 如果是第一行和最后一行，访问所有格子
            // 如果不是，只访问第一列和最后一列的格子
            int step = i == 0 || i == m - 1 ? 1 : n - 1;
            for (int j = 0; j < n; j += step)
                dfs(grid, i, j);
        }

        int ans = 0;
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (grid[i][j] == 0) { // 从没有访问过的 0 出发
                    ans++; // 一定是封闭岛屿
                    dfs(grid, i, j);
                }
            }
        }
        return ans;
    }

    private void dfs(int[][] grid, int x, int y) {
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[x].length || grid[x][y] != 0)
            return;
        grid[x][y] = 1; // 标记 (x,y) 被访问，避免重复访问
        dfs(grid, x - 1, y);
        dfs(grid, x + 1, y);
        dfs(grid, x, y - 1);
        dfs(grid, x, y + 1);
    }
}

python3 解法, 执行用时: 68 ms, 内存消耗: 16.8 MB, 提交时间: 2023-06-18 09:35:56

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        def dfs(x: int, y: int) -> None:
            grid[x][y] = 1  # 标记 (x,y) 被访问，避免重复访问
            # 访问四方向的 0
            for i, j in (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1):
                if 0 <= i < m and 0 <= j < n and grid[i][j] == 0:
                    dfs(i, j)

        for i in range(m):
            # 如果是第一行和最后一行，访问所有格子
            # 如果不是，只访问第一列和最后一列的格子
            step = 1 if i == 0 or i == m - 1 else n - 1
            for j in range(0, n, step):
                if grid[i][j] == 0:  # 从没有访问过的 0 出发
                    dfs(i, j)

        ans = 0
        for i in range(1, m - 1):
            for j in range(1, n - 1):
                if grid[i][j] == 0:  # 从没有访问过的 0 出发
                    ans += 1  # 一定是封闭岛屿
                    dfs(i, j)
        return ans

python3 解法, 执行用时: 68 ms, 内存消耗: 15.2 MB, 提交时间: 2022-07-20 10:35:42

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        def dfs(grid, r, c):
            if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]):
                return False
            if grid[r][c] == 1:
                return True
            grid[r][c] = 1

            return dfs(grid, r-1, c) & dfs(grid, r+1, c) & dfs(grid, r, c-1) & dfs(grid, r, c+1)

        count = 0
        r, c = len(grid), len(grid[0])
        for i in range(r):
            for j in range(c):
                if grid[i][j] == 0:
                    result = dfs(grid, i, j)
                    if result:
                        count += 1
        return count

上一题

下一题

详情