1254.统计封闭岛屿的数目

链接：1254.统计封闭岛屿的数目
难度：Medium
标签：深度优先搜索、广度优先搜索、并查集、数组、矩阵
简介：二维矩阵 grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，封闭岛是一个 完全 由1包围（左、上、右、下）的岛。请返回 封闭岛屿 的数目。

题解 1 - cpp

• 编辑时间：2023-06-18
• 执行用时：20ms
• 内存消耗：13MB
• 编程语言：cpp
• 解法介绍：bfs。

#define X first
#define Y second
#define pii pair<int, int>
vector<vector<int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
class Solution {
public:
    int closedIsland(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size(), res = 0;
        bool used[100][100] = {0};
        auto check = [&](int i, int j) {
            bool res = true;
            queue<pii> q;
            q.push(make_pair(i, j));
            used[i][j] = true;
            while (q.size()) {
                auto cur = q.front();
                q.pop();
                for (auto &dir : dirs) {
                    int ni = cur.X + dir[0], nj = cur.Y + dir[1];
                    if (ni < 0 || ni >= n || nj < 0 || nj >= m || grid[ni][nj] == 1 || used[ni][nj]) continue;
                    if (ni == 0 || ni == n - 1 || nj == 0 || nj == m - 1) res = false;
                    q.push(make_pair(ni, nj));
                    used[ni][nj] = true;
                }
            }
            return res;
        };
        for (int i = 1; i < n - 1; i++) {
            for (int j = 1; j < m - 1; j++) {
                if (grid[i][j] == 0 && !used[i][j] && check(i, j)) res += 1;
            }
        }
        return res;
    }
};