【LetMeFly】1254.统计封闭岛屿的数目：广度优先搜索BFS

力扣题目链接：https://leetcode.cn/problems/number-of-closed-islands/

二维矩阵 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

方法一：BFS，先四周后中间

首先我们写一个BFS函数，从一个“0”开始广搜，将与之相连的所有“0”全部标记为“1”。

这样，我们只需要首先遍历给定地图的四周，将与四周相连的“0”送入BFS函数并标记为“1”，

接着遍历中间的“0”，将中间相邻的“0”标记为“1”的同时，记录下标记次数即为“封闭岛屿”的个数。

时间复杂度$O(n\times m)$，其中$size(grid)=n\times m$
空间复杂度$O(n\times m)$

AC代码

C++

/*
 * @LastEditTime: 2023-06-18 13:32:17
 */
typedef pair<int, int> pii;

const int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

class Solution {
private:
    void mark(vector<vector<int>>& grid, int x, int y) {
        queue<pii> q;
        q.push({x, y});
        grid[x][y] = 1;
        while (q.size()) {
            auto [x, y] = q.front();
            q.pop();
            for (int d = 0; d < 4; d++) {
                int tx = x + directions[d][0];
                int ty = y + directions[d][1];
                if (tx >= 0 && tx < grid.size() && ty >= 0 && ty < grid[0].size() && grid[tx][ty] == 0) {
                    q.push({tx, ty});
                    grid[tx][ty] = 1;
                }
            }
        }
    }
public:
    int closedIsland(vector<vector<int>>& grid) {
        // 四周的0视为1
        for (int i = 0; i < grid.size(); i++) {
            if (grid[i][0] == 0) {
                mark(grid, i, 0);
            }
            if (grid[i][grid[0].size() - 1] == 0) {
                mark(grid, i, grid[0].size() - 1);
            }
        }
        for (int j = 0; j < grid[0].size(); j++) {
            if (grid[0][j] == 0) {
                mark(grid, 0, j);
            }
            if (grid[grid.size() - 1][j] == 0) {
                mark(grid, grid.size() - 1, j);
            }
        }
        // 统计中间岛屿数量
        int ans = 0;
        for (int i = 1; i < grid.size() - 1; i++) {
            for (int j = 1; j < grid[0].size() - 1; j++) {
                if (grid[i][j] == 0) {
                    mark(grid, i, j);
                    ans++;
                }
            }
        }
        return ans;
    }
};

Python

'''
LastEditTime: 2023-06-18 13:52:12
'''
# from typing import List


directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]

class Solution:
    def mark(self, grid: List[List[int]], x, y) -> None:
        q = []
        grid[x][y] = 1
        q.append((x, y))
        while q:
            x, y = q.pop()
            for dx, dy in directions:
                tx = dx + x
                ty = dy + y
                if 0 <= tx < len(grid) and 0 <= ty < len(grid[0]) and grid[tx][ty] == 0:
                    grid[tx][ty] = 1
                    q.append((tx, ty))
        
    def closedIsland(self, grid: List[List[int]]) -> int:
        for i in range(len(grid)):
            if grid[i][0] == 0:
                self.mark(grid, i, 0)
            if grid[i][-1] == 0:
                self.mark(grid, i, len(grid[0]) - 1)
        for j in range(len(grid[0])):
            if grid[0][j] == 0:
                self.mark(grid, 0, j)
            if grid[-1][j] == 0:
                self.mark(grid, len(grid) - 1, j)
        
        ans = 0
        for i in range(1, len(grid) - 1):
            for j in range(1, len(grid[0]) - 1):
                if grid[i][j] == 0:
                    self.mark(grid, i, j)
                    ans += 1
        return ans

方法二：BFS，连着边则视为不封闭岛屿

依次遍历地图中每一个节点，遇到一个土地则从该土地开始广搜，将与之相连的所有土地全部标记为水域。

如果遍历过程中遇到了地图边界，则该岛屿是非封闭岛屿，不累加答案。

时间复杂度$O(n\times m)$，其中$size(grid)=n\times m$
空间复杂度$O(n\times m)$

AC代码

C++

/*
 * @LastEditTime: 2026-10-25 09:17:30
 */
class Solution {
private:
    int n, m;
    static constexpr int dirs[][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};

    bool isCenter(int i, int j) {  // 是否不是四周这一圈
        return i && i != n - 1 && j && j != m - 1;
    }

    bool inGrid(int i, int j) {
        return i >= 0 && i < n && j >=0 && j < m;
    }
public:
    int closedIsland(vector<vector<int>>& grid) {
        n = grid.size(), m = grid[0].size();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j]) {
                    continue;
                }
                // 新土地
                grid[i][j] = 1;
                bool ok = isCenter(i, j);
                queue<pair<int, int>> q;
                q.push({i, j});
                while (!q.empty()) {
                    auto [x, y] = q.front();
                    q.pop();
                    for (auto[dx, dy] : dirs) {
                        int nx = x + dx, ny = y + dy;
                        if (!inGrid(nx, ny) || grid[nx][ny]) {
                            continue;
                        }
                        grid[nx][ny] = 1;
                        ok &= isCenter(nx, ny);
                        q.push({nx, ny});
                    }
                }
                ans += ok;
            }
        }
        return ans;
    }
};

Python

'''
LastEditTime: 2026-10-25 09:24:54
'''
from typing import List

dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]

class Solution:
    def isCenter(self, i: int, j: int) -> bool:
        return 0 < i < self.n - 1 and 0 < j < self.m - 1
    
    def inGrid(self, i: int, j: int) -> bool:
        return 0 <= i < self.n and 0 <= j < self.m
    
    def closedIsland(self, grid: List[List[int]]) -> int:
        self.n = len(grid)
        self.m = len(grid[0])
        ans = 0
        for i, line in enumerate(grid):
            for j, v in enumerate(line):
                if v:
                    continue
                grid[i][j] = 1
                ok = self.isCenter(i, j)
                q = [(i, j)]
                while q:
                    x, y = q.pop()
                    for dx, dy in dirs:
                        nx, ny = x + dx, y + dy
                        if not self.inGrid(nx, ny) or grid[nx][ny]:
                            continue
                        grid[nx][ny] = 1
                        ok &= self.isCenter(nx, ny)
                        q.append((nx, ny))
                ans += ok
        return ans

Java

/*
 * @LastEditTime: 2026-10-25 12:56:37
 */
import java.util.Queue;
import java.util.LinkedList;

class Solution {
    private int n, m;
    private final int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    private boolean isCenter(int i, int j) {
        return 0 < i && i < n - 1 && 0 < j && j < m - 1;
    }

    private boolean inGrid(int i, int j) {
        return 0 <= i && i < n && 0 <= j && j < m;
    }

    public int closedIsland(int[][] grid) {
        n = grid.length;
        m = grid[0].length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    continue;
                }
                grid[i][j] = 1;
                boolean ok = isCenter(i, j);
                Queue<int[]> q = new LinkedList<>();
                q.offer(new int[]{i, j});
                while (!q.isEmpty()) {
                    int[] top = q.poll();
                    int x = top[0], y = top[1];
                    for (int[] d : dirs) {
                        int nx = x + d[0], ny = y + d[1];
                        if (!inGrid(nx, ny) || grid[nx][ny] == 1) {
                            continue;
                        }
                        grid[nx][ny] = 1;
                        ok &= isCenter(nx, ny);
                        q.offer(new int[]{nx, ny});
                    }
                }
                if (ok) {
                    ans++;
                }
            }
        }
        return ans;
    }
}

Go

/*
 * @LastEditTime: 2026-10-25 12:16:55
 */
package main

func isCenter1254(i, j, n, m int) bool {
    return 0 < i && i < n - 1 && 0 < j && j < m - 1
}

func inGrid1254(i, j, n, m int) bool {
    return 0 <= i && i < n && 0 <= j && j < m
}

var dirs1254 = [4][2]int{{0, -1}, {0, 1}, {1, 0}, {-1, 0}}

func closedIsland(grid [][]int) (ans int) {
    n, m := len(grid), len(grid[0])
    for i, line := range grid {
        for j, v := range line {
            if v == 1 {
                continue
            }
            ok := isCenter1254(i, j, n, m)
            grid[i][j] = 1
            q := [][2]int{{i, j}}
            for len(q) > 0 {
                top := q[len(q) - 1]
                q = q[:len(q) - 1]
                x, y := top[0], top[1]
                for _, d := range dirs1254 {
                    nx, ny := x + d[0], y + d[1]
                    if !inGrid1254(nx, ny, n, m) || grid[nx][ny] == 1 {
                        continue
                    }
                    grid[nx][ny] = 1
                    ok = ok && isCenter1254(nx, ny, n, m)  // go没有bool的&
                    q = append(q, [2]int{nx, ny})
                }
            }
            if ok {
                ans++
            }
        }
    }
    return
}

Rust

/*
 * @LastEditTime: 2026-10-25 16:19:59
 */
use std::collections::VecDeque;

impl Solution {
    const DIRS: [(isize, isize); 4] = [(-1, 0), (1, 0), (0, 1), (0, -1)];  // 注意防止usize到-1

    fn is_center(i: usize, j: usize, n: usize, m: usize) -> bool {
        0 < i && i < n - 1 && 0 < j && j < m - 1
    }

    fn in_grid(i: isize, j: isize, n: usize, m: usize) -> bool {
        0 <= i && i < n as isize && 0 <= j && j < m as isize
    }

    pub fn closed_island(mut grid: Vec<Vec<i32>>) -> i32 {
        let n = grid.len();
        let m = grid[0].len();
        let mut ans = 0;
        for i in 0..n {
            for j in 0..m {
                if grid[i][j] == 1 {
                    continue;
                }
                grid[i][j] = 1;
                let mut ok = Self::is_center(i, j, n, m);
                let mut q = VecDeque::new();
                q.push_back((i, j));
                while let Some((x, y)) = q.pop_front() {
                    for &(dx, dy) in &Self::DIRS {
                        let nx = x as isize + dx;
                        let ny = y as isize + dy;
                        if !Self::in_grid(nx, ny, n, m){
                            continue;
                        }
                        let (nx, ny) = (nx as usize, ny as usize);
                        if grid[nx][ny] == 1 {
                            continue;
                        }
                        grid[nx][ny] = 1;
                        ok &= Self::is_center(nx, ny, n, m);
                        q.push_back((nx, ny));
                    }
                }
                ans += if ok {
                    1
                } else {
                    0
                }
            }
        }
        ans
    }
}

End

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源

题解 > LeetCode

#BFS #LeetCode #中等 #图 #并查集 #广度优先搜索 #数组 #深度优先搜索 #矩阵 #题解

1254.统计封闭岛屿的数目：广度优先搜索BFS

https://blog.letmefly.xyz/2023/06/18/LeetCode 1254.统计封闭岛屿的数目/

作者

Tisfy

发布于

2023年6月18日

许可协议

1262.可被三整除的最大和：时间O(n)空间O(1) 上一篇

2481.分割圆的最少切割次数下一篇