1254. Number of Closed Islands

Given a 2D `grid` consists of `0s` (land) and `1s` (water).  An  island  is a maximal 4-directionally connected group of `0s` and a  closed island  is an island totally (all left, top, right, bottom) surrounded by `1s.`

Return the number of  closed islands.

Example 1:

``````Input: 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]]
Output: 2
Explanation:
Islands in gray are closed because they are completely surrounded by water (group of 1s).
``````

Example 2:

``````Input: grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
Output: 1
``````

Example 3:

``````Input: 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]]
Output: 2
``````

Constraints:

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

``````class Solution {
public:
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 ((i == 0 || i == m - 1 || j == 0 || j == n - 1) && grid[i][j] == 0) {
dfs(grid, i, j);
}
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] != 0) continue;
dfs(grid, i, j);
++res;
}
}
return res;
}
void dfs(vector<vector<int>>& grid, int i, int j) {
int m = grid.size(), n = grid[0].size();
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != 0) return;
grid[i][j] = 2;
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
}
};
``````

``````class Solution {
public:
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 i, int j) {
int m = grid.size(), n = grid[0].size();
if (i < 0 || i >= m || j < 0 || j >= n) return 0;
if (grid[i][j] > 0) return 1;
grid[i][j] = 2;
return dfs(grid, i + 1, j) * dfs(grid, i - 1, j) * dfs(grid, i, j + 1) * dfs(grid, i, j - 1);
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1254

https://leetcode.com/problems/number-of-closed-islands/

https://leetcode.com/problems/number-of-closed-islands/discuss/425150/JavaC%2B%2B-with-picture-Number-of-Enclaves

https://leetcode.com/problems/number-of-closed-islands/discuss/426294/JavaPython-3-DFS-BFS-and-Union-Find-codes-w-brief-explanation-and-analysis.

LeetCode All in One 题目讲解汇总(持续更新中…)

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation