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 <= 1000 <= grid[i][j] <=1
Solution: DFS/Backtracking
For each connected component, if it can reach the boundary then it’s not a closed island.
Time complexity: O(n*m)
Space complexity: O(n*m)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua class Solution { public: int closedIsland(vector<vector<int>>& grid) { const int n = grid.size(); const int m = grid[0].size(); function<int(int, int)> dfs = [&](int x, int y) { if (x < 0 || y < 0 || x >= m || y >= n) return 0; if (grid[y][x]++) return 1; return dfs(x + 1, y) & dfs(x - 1, y) & dfs(x, y + 1) & dfs(x, y - 1); }; int ans = 0; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) if (!grid[i][j]) ans += dfs(j, i); return ans; } }; |