forked from kamyu104/LeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
number-of-closed-islands.cpp
40 lines (38 loc) · 1.1 KB
/
number-of-closed-islands.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// Time: O(m * n)
// Space: O(1)
class Solution {
public:
int closedIsland(vector<vector<int>>& grid) {
for (int j = 0; j < grid[0].size(); ++j) {
fill(&grid, 0, j);
fill(&grid, grid.size() - 1, j);
}
for (int i = 1; i + 1 < grid.size(); ++i) {
fill(&grid, i, 0);
fill(&grid, i, grid[0].size() - 1);
}
int result = 0;
for (int i = 1; i + 1 < grid.size(); ++i) {
for (int j = 1; j + 1 < grid[0].size(); ++j) {
if (fill(&grid, i, j)) {
++result;
}
}
}
return result;
}
private:
bool fill(vector<vector<int>> *grid, int i, int j) {
static vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
if (i < 0 || j < 0 ||
i >= grid->size() || j >= (*grid)[i].size() ||
(*grid)[i][j]) {
return false;
}
(*grid)[i][j] = 1;
for (const auto& [dx, dy] : directions) {
fill(grid, i + dx, j + dy);
}
return true;
}
};