leetcode

commit feda53f64a3c1e765a8886a0ac3ef5ad9722b9b5
parent ebc69b929dabb079751897ecabca77f2f940e4ec
Author: Jack Sangdahl <jack@pngu.org>
Date:   Sat,  1 Nov 2025 18:13:25 -0600

2257. count unguarded cells in the grid

Diffstat:
M
count_unguard_cells_grid.c
 | 
78
+++++++++++++++++++++++++++++++++++++++++-------------------------------------
M
count_unguard_cells_grid.py
 | 
52
+++++++++++++++++++++++++++-------------------------

2 files changed, 68 insertions(+), 62 deletions(-)
diff --git a/count_unguard_cells_grid.c b/count_unguard_cells_grid.c
@@ -1,6 +1,5 @@
 // 2257. Count Unguarded Cells in the Grid
 #include "leetcode.h"
-#include <stdio.h>
 
 /*
  * you are given two integers 'm' and 'n' representing a 0-indexed 'm x n' grid.
@@ -16,53 +15,58 @@
 int countUnguarded(int m, int n, int **guards, int guardsSize,
                    int *guardsColSize, int **walls, int wallsSize,
                    int *wallsColSize) {
-  int unguarded = m * n;
-  char *grid = (char *)calloc(unguarded, sizeof(char));
-  for (int i = 0; i < guardsSize; i++) {
-    grid[guards[i][0] * n + guards[i][1]] = 1;
-    unguarded--;
+  int **vis = (int **)malloc(m * sizeof(int *));
+  for (int i = 0; i < m; i++)
+    vis[i] = (int *)malloc(n * sizeof(int));
+  for (int i = 0; i < guardsSize; ++i) {
+    int r = guards[i][0];
+    int c = guards[i][1];
+    vis[r][c] = 2;
   }
-  for (int i = 0; i < wallsSize; i++) {
-    grid[walls[i][0] * n + walls[i][1]] = 2;
-    unguarded--;
+  for (int i = 0; i < wallsSize; ++i) {
+    int r = walls[i][0];
+    int c = walls[i][1];
+    vis[r][c] = 3;
   }
-  for (int i = 0; i < guardsSize; i++) {
-    int row = guards[i][0], col = guards[i][1];
-    for (int c = col + 1; c < n; c++) {
-      if (grid[row * n + c] == 1 || grid[row * n + c] == 2)
+  for (int i = 0; i < guardsSize; ++i) {
+    int r = guards[i][0];
+    int c = guards[i][1];
+    int left = c - 1, right = c + 1;
+    int up = r - 1, down = r + 1;
+    while (left >= 0) {
+      if (vis[r][left] == 3 || vis[r][left] == 2)
         break;
-      if (!grid[row * n + c]) {
-        grid[row * n + c] = 3;
-        unguarded--;
-      }
+      vis[r][left] = 1;
+      left--;
     }
-    for (int c = col - 1; c >= 0; c--) {
-      if (grid[row * n + c] == 1 || grid[row * n + c] == 2)
+    while (right < n) {
+      if (vis[r][right] == 3 || vis[r][right] == 2)
         break;
-      if (!grid[row * n + c]) {
-        grid[row * n + c] = 3;
-        unguarded--;
-      }
+      vis[r][right] = 1;
+      right++;
     }
-    for (int r = row + 1; r < m; r++) {
-      if (grid[r * n + col] == 1 || grid[r * n + col] == 2)
+    while (up >= 0) {
+      if (vis[up][c] == 3 || vis[up][c] == 2)
         break;
-      if (!grid[r * n + col]) {
-        grid[r * n + col] = 3;
-        unguarded--;
-      }
+      vis[up][c] = 1;
+      up--;
     }
-    for (int r = row - 1; r >= 0; r--) {
-      if (grid[r * n + col] == 1 || grid[r * n + col] == 2)
+    while (down < m) {
+      if (vis[down][c] == 3 || vis[down][c] == 2)
         break;
-      if (!grid[r * n + col]) {
-        grid[r * n + col] = 3;
-        unguarded--;
-      }
+      vis[down][c] = 1;
+      down++;
     }
   }
-  free(grid);
-  return unguarded;
+  int ans = 0;
+  for (int i = 0; i < m; i++)
+    for (int j = 0; j < n; ++j)
+      if (!vis[i][j])
+        ans++;
+  for (int i = 0; i < m; i++)
+    free(vis[i]);
+  free(vis);
+  return ans;
 }
 
 int main() {
diff --git a/count_unguard_cells_grid.py b/count_unguard_cells_grid.py
@@ -21,35 +21,37 @@ class Solution(object):
         :type walls: List[List[int]]
         :rtype: int
         """
-        vis = [[0] * n for _ in range(m)]
-        for val in walls:
-            vis[val[0]][val[1]] = 2
-        for val in guards:
-            vis[val[0]][val[1]] = 3
-        for val in guards:
-            row, col = val[0], val[1]
-            for i in range(row + 1, m):
-                if vis[i][col] in (2, 3):
+        vis = [[0 for _ in range(n)] for _ in range(m)]
+        for i in guards:
+            vis[i[0]][i[1]] = 2
+        for i in walls:
+            vis[i[0]][i[1]] = 3
+        for i in range(len(guards)):
+            r = guards[i][0]
+            c = guards[i][1]
+            left, right = c - 1, c + 1
+            up, down = r - 1, r + 1
+            while left >= 0:
+                if vis[r][left] == 3 or vis[r][left] == 2:
                     break
-                vis[i][col] = 1
-            for i in range(row - 1, -1, -1):
-                if vis[i][col] in (2, 3):
+                vis[r][left] = 1
+                left -= 1
+            while right < n:
+                if vis[r][right] == 3 or vis[r][right] == 2:
                     break
-                vis[i][col] = 1
-            for i in range(col + 1, n):
-                if vis[row][i] in (2, 3):
+                vis[r][right] = 1
+                right += 1
+            while up >= 0:
+                if vis[up][c] == 3 or vis[up][c] == 2:
                     break
-                vis[row][i] = 1
-            for i in range(col - 1, -1, -1):
-                if vis[row][i] in (2, 3):
+                vis[up][c] = 1
+                up -= 1
+            while down < m:
+                if vis[down][c] == 3 or vis[down][c] == 2:
                     break
-                vis[row][i] = 1
-        unguarded = 0
-        for i in range(m):
-            for j in range(n):
-                if vis[i][j] == 0:
-                    unguarded += 1
-        return unguarded
+                vis[down][c] = 1
+                down += 1
+        return sum(1 for i in range(m) for j in range(n) if vis[i][j] == 0)
 
 
 if __name__ == "__main__":