Sponsored
Sponsored
The grid can be viewed as a graph where each cell is a node connected to its four possible neighbors. To identify closed islands, we can use a DFS approach starting from any cell containing 0 (cell of land). This DFS should mark the entire island by changing those 0s to a visited flag, such as -1. During the traversal, if any part of the island reaches the grid's boundary, it cannot be a closed island.
For each unvisited 0, if it forms a complete island (i.e., it does not reach the boundary), we increment the closed island count. We examine cells systematically, ensuring that all possible islands are accounted for.
Time Complexity: O(m * n), where m is the number of rows, and n is the number of columns. Each cell is visited once.
Space Complexity: O(m * n) due to the recursion stack.
1#include <vector>
2#include <iostream>
3
4using namespace std;
5
6void dfs(vector<vector<int>>& grid, int x, int y, bool& isClosed) {
7 int rows = grid.size();
8 int cols = grid[0].size();
9 if (x < 0 || y < 0 || x >= rows || y >= cols) {
10 isClosed = false;
11 return;
12 }
13 if (grid[x][y] == 1 || grid[x][y] == -1) return;
14 grid[x][y] = -1;
15 dfs(grid, x + 1, y, isClosed);
16 dfs(grid, x - 1, y, isClosed);
17 dfs(grid, x, y + 1, isClosed);
18 dfs(grid, x, y - 1, isClosed);
19}
20
21int closedIsland(vector<vector<int>>& grid) {
22 int count = 0;
23 for (int i = 0; i < grid.size(); i++) {
24 for (int j = 0; j < grid[0].size(); j++) {
25 if (grid[i][j] == 0) {
26 bool isClosed = true;
27 dfs(grid, i, j, isClosed);
28 if (isClosed) {
29 count++;
30 }
31 }
32 }
33 }
34 return count;
35}
36
37int main() {
38 vector<vector<int>> 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},
39 {1,0,0,0,0,1,0,1}, {1,1,1,1,1,1,1,0}};
40 cout << closedIsland(grid) << endl;
41 return 0;
42}The C++ solution employs a similar DFS technique as the C solution, iterating over each cell and checking for a closed island. The grid is modified in place to mark visited cells. The boolean flag ensures we account for boundary-touching islands.
This approach employs BFS to traverse the islands. By leveraging a queue, we can iteratively explore all 0-connected land cells starting from each unvisited land cell. If during any BFS iteration, we find ourselves at the boundary or edge of the grid, the ongoing island is not closed.
Using BFS here can make iterative exploration more intuitive and can be preferred in languages where managing stacks explicitly is a common challenge, although the core logic of edge-checking remains similar.
Time Complexity: O(m * n), where m is the number of rows, and n is the number of columns.
Space Complexity: O(m + n) due to the queue memory usage during BFS.
1import java.util.LinkedList;
2import java.util.Queue;
3
4class Solution {
5 public int closedIsland(int[][] grid) {
6 int count = 0;
7 for (int i = 0; i < grid.length; i++) {
8 for (int j = 0; j < grid[0].length; j++) {
9 if (grid[i][j] == 0) {
10 if (bfs(grid, i, j)) {
11 count++;
12 }
13 }
14 }
15 }
16 return count;
17 }
18
19 private boolean bfs(int[][] grid, int startX, int startY) {
20 Queue<int[]> queue = new LinkedList<>();
21 queue.offer(new int[]{startX, startY});
22 int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
23 grid[startX][startY] = -1;
24 boolean isClosed = true;
25
26 while (!queue.isEmpty()) {
27 int[] cell = queue.poll();
28 for (int[] dir : directions) {
29 int nx = cell[0] + dir[0];
30 int ny = cell[1] + dir[1];
31 if (nx < 0 || ny < 0 || nx >= grid.length || ny >= grid[0].length) {
32 isClosed = false;
33 } else if (grid[nx][ny] == 0) {
34 grid[nx][ny] = -1;
35 queue.offer(new int[]{nx, ny});
36 }
37 }
38 }
39 return isClosed;
40 }
41}
42The Java implementation uses BFS with a Queue. It traverses the island's connected components and checks for boundary connections. The queue efficiently manages the exploration state.