统计封闭岛屿的数目

题目链接

有一个二维矩阵 grid，每个位置要么是陆地（记号为 0 ）要么是水域（记号为 1 ）。

我们从一块陆地出发，每次可以往上下左右 4 个方向相邻区域走，能走到的所有陆地区域，我们将其称为一座「岛屿」。

如果一座岛屿完全由水域包围，即陆地边缘上下左右所有相邻区域都是水域，那么我们将其称为 「封闭岛屿」。

请返回封闭岛屿的数目。

示例:

20220123001725-2022-01-23-00-17-26

输入：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 区域包围）

思路

解法一：

解题的关键在于如何判断 「封闭岛屿」。dfs思路如下：

  1. 如果遇到 0, 即陆地，则以此点进行扩散遍历，将访问过的节点置为1；
  2. dfs遍历的时候需要判断是否和边界相连，如果相连则证明不是「封闭岛屿」，dfs遍历的结果为0;
  3. 累加「封闭岛屿」的结果。
class Solution {
public:
    int m, n;
    int closedIsland(vector<vector<int>>& grid) {
        int res = 0;
        m = grid.size();
        n = grid[0].size();

        for (int i = 0; i < m;i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) { // 陆地，开始遍历
                    res += dfs(grid, i, j);
                }
            }
        }
        return res;
    }

    int dfs(vector<vector<int>>& grid, int x, int y) {
        if (x < 0 || x >= m || y < 0 || y >= n) {
            return 0;
        }
        if (grid[x][y] == 1) { //碰到水域(值为1的点)就返回封闭岛屿个数1，表示该岛屿可能就是一个封闭岛屿
            return 1;
        }
        grid[x][y] = 1;

        // 如果碰到陆地(值为0的点)就继续向该陆地的四个方向遍历，同时将该陆地标记为1，表示这个位置已经遍历过了。
        int vx[] = {0, 1, 0, -1};
        int vy[] = {1, 0, -1, 0};
        int res = 1;
        for (int i = 0; i < 4; i++) {
            res = min(res, dfs(grid, x + vx[i], y + vy[i])); // 四个方向进行遍历，去四个方向的最小值，若有一个为0，则到达边界，证明不是封闭岛屿
        }
        return res;
    }
};

解法二

也可以使用 BFS 方法，思路如下：

  1. 将当前陆地的位置加入到队列中，然后取出当前位置，并将它标记为1，表示它已经遍历过了；
  2. 将它四个方向也为陆地的位置加入到队列中，一直循环，直到队列为空；
  3. 在循环的过程中我们需要判断是否走出了边界，如果走出了边界就说明该位置所在的岛屿不是封闭岛屿。
class Solution {
public:
    int m, n;
    int closedIsland(vector<vector<int>>& grid) {
        int res = 0;
        m = grid.size();
        n = grid[0].size();

        for (int i = 0; i < m;i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    res += bfs(grid, i, j);
                }
            }
        }
        return res;
    }

    int bfs(vector<vector<int>> &grid, int x, int y)
    {
        int res = 1;
        queue<vector<int>> q;
        q.push({x, y});

        while (!q.empty())
        {
            vector<int> pos(q.front());
            q.pop();
            grid[pos[0]][pos[1]] = 1;
            int vx[] = {0, 1, 0, -1};
            int vy[] = {1, 0, -1, 0};

            for (int i = 0; i < 4; i++)
            {
                int nx = pos[0] + vx[i];
                int ny = pos[1] + vy[i];

                if (nx < 0 || nx >= m || ny < 0 || ny >= n)
                { // 若达到边界上，则证明不是封闭岛屿
                    res = 0;
                    continue;
                }

                if (grid[nx][ny] == 0)
                { // 将其他邻近的陆地添加到队列中
                    q.push({nx, ny});
                }
            }
        }
        return res;
    }

};