题目描述

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

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

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

请返回封闭岛屿的数目。

样例

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

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

算法

(宽度优先遍历 / Flood Fill) O(nm)

典型的宽度优先遍历问题，只不过这里要求的连通块不与边界相邻。
我们在遍历过程中，判断一下是否遇到过边界，如果遇到过，则此次遍历结果为 false。注意，返回 false 也需要在完全遍历完当前的连通块后。

时间复杂度

每个位置遍历一次，故时间复杂度为 O(nm)。

空间复杂度

需要额外的队列空间存放遍历的点（若采用深度优先遍历则需要系统栈空间）。
故空间复杂度为 O(nm)。

C 代码

typedef struct{
    int x;
    int y;
}Node;

Node queue[100 * 100];
int hh = 0, tt = -1;

bool bfs(int x, int y, int** grid, int gridSize, int* gridColSize)
{
    int n = gridSize, m = *gridColSize;
    int dx[4] = {0, 1, 0, -1}; // 从y正轴 逆时针走
    int dy[4] = {1, 0, -1, 0};
    hh = 0;
    tt = -1;

    tt ++ ;
    queue[tt].x = x;
    queue[tt].y = y;

    bool flag = true;
    while (hh <= tt) {
        Node sta = queue[hh];
        hh ++ ;
        for (int i = 0; i < 4; i ++ ) {
            int x = sta.x + dx[i];
            int y = sta.y + dy[i];
            if (x < 0 || x >= n || y < 0 || y >= m) {
                flag = false;
                continue;
            }

            if (grid[x][y] == 0) {
                grid[x][y] = 1;
                tt ++ ;
                queue[tt].x = x;
                queue[tt].y = y;
            }
        }
    }

    return flag;
}

int closedIsland(int** grid, int gridSize, int* gridColSize){
    int ans = 0;
    for (int i = 0; i < gridSize; i ++ ) { // 行给了
        for (int j = 0; j < *gridColSize; j ++ ) { // 列给了
            if (grid[i][j] == 0) {
                ans += bfs(i, j, grid, gridSize, gridColSize);
            }
        }
    }

    return ans;
}