leetcode

commit b913661b53a8cb74715a2e87eafe17f7f9419d2c
parent c2bc609ab93ea55966b9b67fd736ab168a013690
Author: Jack Sangdahl <jack@pngu.org>
Date:   Sat, 14 Feb 2026 20:43:56 -0700

1020. number of enclaves

Diffstat:
M
num_enclaves.c
 | 
83
++++++++++++++++++++++++++++++++++++-------------------------------------------
A
num_enclaves.py
 | 
41
+++++++++++++++++++++++++++++++++++++++++

2 files changed, 79 insertions(+), 45 deletions(-)
diff --git a/num_enclaves.c b/num_enclaves.c
@@ -1,6 +1,5 @@
 // 1020. Number of Enclaves
-#include <stdbool.h>
-#include <stdio.h>
+#include "leetcode.h"
 
 /*
  * given an 'm * n' binary matrix grid, where 0 represents a sea
@@ -11,55 +10,49 @@
  * boundary of the grid in any number of moves.
  */
 
-int u_find(int *u, int val) {
-  if (u[val] == val)
-    return val;
-  return u_find(u, u[val]);
-}
-
-bool u_set(int *u, int a, int b) {
-  int find_a = u_find(u, a), find_b = u_find(u, b);
-  if (find_a == find_b)
-    return false;
-  u[find_a] = u[find_b];
-  return true;
-}
-
-void bfs(int **grid, int row, int col, int i, int j) {
-  if (i < 0 || i >= row || j < 0 || j >= col)
-    return;
-  if (!grid[i][j])
+void dfs(int **grid, int r, int c, int n, int m) {
+  if (r < 0 || c < 0 || r > n - 1 || c > m - 1 || !grid[r][c] ||
+      grid[r][c] == -1)
     return;
-  grid[i][j] = 0;
-  bfs(grid, row, col, i - 1, j);
-  bfs(grid, row, col, i + 1, j);
-  bfs(grid, row, col, i, j - 1);
-  bfs(grid, row, col, i, j + 1);
+  grid[r][c] = -1;
+  dfs(grid, r + 1, c, n, m);
+  dfs(grid, r - 1, c, n, m);
+  dfs(grid, r, c + 1, n, m);
+  dfs(grid, r, c - 1, n, m);
 }
 
-int numEnclaves(int **grid, int grid_size, int *grid_col_size) {
-  int row = grid_size, col = *grid_col_size;
-  for (int i = 0; i < col; i++)
-    bfs(grid, row, col, 0, i);
-  for (int i = 0; i < col; i++)
-    bfs(grid, row, col, row - 1, i);
-  for (int i = 0; i < row; i++)
-    bfs(grid, row, col, i, 0);
-  for (int i = 0; i < row; i++)
-    bfs(grid, row, col, i, col - 1);
-  int ans = 0;
-  for (int i = 0; i < row; i++)
-    for (int j = 0; j < col; j++)
-      if (grid[i][j])
+int numEnclaves(int **grid, int gridSize, int *gridColSize) {
+  int n = gridSize, m = gridColSize[0], ans = 0;
+  for (int c = 0; c < m; c++) {
+    if (grid[0][c] == 1)
+      dfs(grid, 0, c, n, m);
+    if (grid[n - 1][c] == 1)
+      dfs(grid, n - 1, c, n, m);
+  }
+  for (int r = 1; r < n - 1; r++) {
+    if (grid[r][0] == 1)
+      dfs(grid, r, 0, n, m);
+    if (grid[r][m - 1] == 1)
+      dfs(grid, r, m - 1, n, m);
+  }
+  for (int r = 0; r < n; r++)
+    for (int c = 0; c < m; c++)
+      if (grid[r][c] == 1)
         ans++;
   return ans;
 }
 
 int main() {
-  int g1[4][4] = {{0, 0, 0, 0}, {1, 0, 1, 0}, {0, 1, 1, 0}, {0, 0, 0, 0}};
-  int g2[4][4] = {{0, 1, 1, 0}, {0, 0, 1, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}};
-  int grid_size = 4;
-  int grid_col_size[] = {4, 4, 4, 4};
-  printf("%d\n", numEnclaves(g1, grid_size, grid_col_size)); // expect: 3
-  printf("%d\n", numEnclaves(g2, grid_size, grid_col_size)); // expect: 3
+  int g1i[4][4] = {{0, 0, 0, 0}, {1, 0, 1, 0}, {0, 1, 1, 0}, {0, 0, 0, 0}};
+  int g2i[4][4] = {{0, 1, 1, 0}, {0, 0, 1, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}};
+  struct two_d_arr *g1 =
+      two_d_arr_init(ARRAY_SIZE(g1i), ARRAY_SIZE(g1i[0]), g1i);
+  struct two_d_arr *g2 =
+      two_d_arr_init(ARRAY_SIZE(g2i), ARRAY_SIZE(g2i[0]), g2i);
+  int r1 = numEnclaves(g1->arr, g1->row_size, g1->col_size);
+  int r2 = numEnclaves(g2->arr, g2->row_size, g2->col_size);
+  printf("%d\n", r1); // expect: 3
+  assert(r1 == 3);
+  printf("%d\n", r2); // expect: 0
+  assert(r2 == 0);
 }
diff --git a/num_enclaves.py b/num_enclaves.py
@@ -0,0 +1,41 @@
+# 1020. Number of Enclaves
+
+"""
+given an 'm  n' binary matrix grid, where 0 represents a sea
+cell and 1 represents a land cell. a move consists of walking
+from one land cell to another adjacent (4-directionally) land
+cell o walking off the boundary of the 'grid'. return number
+of land cells in 'grid' for which we cannot walk off the
+boundary of the grid in any number of moves.
+"""
+
+
+class Solution(object):
+    def numEnclaves(self, grid):
+        """
+        :type grid: List[List[int]]
+        :rtype: int
+        """
+
+        def dfs(i, j):
+            grid[i][j] = 0
+            for r, c in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):
+                if 0 <= r < m and 0 <= c < n and grid[r][c]:
+                    dfs(r, c)
+
+        m, n = len(grid), len(grid[0])
+        for i in range(m):
+            for j in range(n):
+                if grid[i][j] == 1 and (i == 0 or j == 0 or i == m - 1 or j == n - 1):
+                    dfs(i, j)
+        return sum(sum(row) for row in grid)
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(
+        obj.numEnclaves(grid=[[0, 0, 0, 0], [1, 0, 1, 0], [0, 1, 1, 0], [0, 0, 0, 0]])
+    )
+    print(
+        obj.numEnclaves(grid=[[0, 1, 1, 0], [0, 0, 1, 0], [0, 0, 1, 0], [0, 0, 0, 0]])
+    )