This approach uses a depth-first search (DFS) to mark land cells connected to the boundaries. We iterate over the boundary cells of the grid and if a land cell is found, we perform DFS to mark all connected land cells as visited. Finally, we count all remaining unvisited land cells inside the grid, which are considered enclaves.
Time Complexity: O(m * n) as each cell is visited at most once.
Space Complexity: O(m * n) in the worst case due to recursion stack used by DFS.
1#include <stdio.h>
2
3void dfs(int** grid, int m, int n, int i, int j) {
4 if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] == 0) {
5 return;
6 }
7 grid[i][j] = 0; // Marking visited land
8 dfs(grid, m, n, i + 1, j);
9 dfs(grid, m, n, i - 1, j);
10 dfs(grid, m, n, i, j + 1);
11 dfs(grid, m, n, i, j - 1);
12}
13
14int numEnclaves(int** grid, int gridSize, int* gridColSize) {
15 int m = gridSize;
16 int n = *gridColSize;
17 for (int i = 0; i < m; i++) {
18 if (grid[i][0] == 1) {
19 dfs(grid, m, n, i, 0);
20 }
21 if (grid[i][n-1] == 1) {
22 dfs(grid, m, n, i, n-1);
23 }
24 }
25 for (int j = 0; j < n; j++) {
26 if (grid[0][j] == 1) {
27 dfs(grid, m, n, 0, j);
28 }
29 if (grid[m-1][j] == 1) {
30 dfs(grid, m, n, m-1, j);
31 }
32 }
33 int count = 0;
34 for (int i = 0; i < m; i++) {
35 for (int j = 0; j < n; j++) {
36 if (grid[i][j] == 1) {
37 count++;
38 }
39 }
40 }
41 return count;
42}
43This C code defines a function dfs that marks land cells ('1') as water ('0'), effectively marking them as visited. The main function numEnclaves iterates over the borders of the grid. For each unvisited land cell on the border, DFS is called to mark connected land. Finally, it counts all unvisited land cells inside the grid as enclaves.
In this approach, we use a queue to perform BFS to mark land cells connected to the boundaries. By enqueueing each boundary land cell and exploring its neighbors iteratively, we can mark all reachable boundary-connected lands. This is followed by counting the unvisited land cells – those are the enclaves.
Time Complexity: O(m * n).
Space Complexity: O(min(m, n)) considering the queue size in the worst case.
1#include <vector>
2#include <queue>
3using namespace std;
4
5void bfs(vector<vector<int>>& grid, int i, int j) {
6 int m = grid.size(), n = grid[0].size();
7 queue<pair<int, int>> q;
8 q.push({i, j});
9 grid[i][j] = 0;
10 vector<vector<int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
11 while (!q.empty()) {
12 auto [r, c] = q.front();
13 q.pop();
14 for (auto& d : directions) {
15 int newRow = r + d[0], newCol = c + d[1];
16 if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && grid[newRow][newCol] == 1) {
17 grid[newRow][newCol] = 0;
18 q.push({newRow, newCol});
19 }
20 }
21 }
22}
23
24int numEnclaves(vector<vector<int>>& grid) {
25 int m = grid.size(), n = grid[0].size();
26
27 for (int i = 0; i < m; i++) {
28 if (grid[i][0] == 1) bfs(grid, i, 0);
29 if (grid[i][n-1] == 1) bfs(grid, i, n-1);
30 }
31 for (int j = 0; j < n; j++) {
32 if (grid[0][j] == 1) bfs(grid, 0, j);
33 if (grid[m-1][j] == 1) bfs(grid, m-1, j);
34 }
35
36 int count = 0;
37 for (int i = 0; i < m; i++) {
38 for (int j = 0; j < n; j++) {
39 if (grid[i][j] == 1) count++;
40 }
41 }
42 return count;
43}
44The C++ BFS solution employs a queue for expansion of boundary land cells. BFS is initiated on boundary-connected land cells, marking reachable cells as zero. Remaining unvisited land cells constitute the enclaves.