题目描述
有一个二维矩阵 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 区域包围)。
输入:
grid = [[0,0,1,0,0],
[0,1,0,1,0],
[0,1,1,1,0]]
输出:1
输入:
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
算法
(宽度优先遍历 / Flood Fill) $O(nm)$
- 典型的
Flood Fill
问题,只不过这里要求的连通块不与边界相邻。 - 我们在遍历过程中,判断一下是否遇到过边界,如果遇到过,则此次遍历结果为
false
。注意,返回false
也需要在完全遍历完当前的连通块后。
时间复杂度
- 每个位置遍历一次,故时间复杂度为 $O(nm)$。
空间复杂度
- 需要额外的队列空间存放遍历的点(若采用深度优先遍历则需要系统栈空间)。
- 故空间复杂度为 $O(nm)$。
C++ 代码
class Solution {
public:
bool bfs(int x, int y, int n, int m, vector<vector<int>>& grid) {
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
queue<pair<int, int>> q;
q.push(make_pair(x, y));
bool flag = true;
while (!q.empty()) {
auto u = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int tx = u.first + dx[i];
int ty = u.second + dy[i];
if (tx < 0 || tx >= n || ty < 0 || ty >= m) {
flag = false;
continue;
}
if (grid[tx][ty] == 0) {
grid[tx][ty] = 1;
q.push(make_pair(tx, ty));
}
}
}
return flag;
}
int closedIsland(vector<vector<int>>& grid) {
int 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] == 0)
ans += bfs(i, j, n, m, grid);
return ans;
}
};
这里有点不太明白
返回 false 也需要在全部遍历结束后。
就是如果遇到边界需要返回
false
时,需要把当前连通块都遍历到后再返回~