aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-11-21 12:14:23 -0700
committerJack Sangdahl <[email protected]>2024-11-21 12:14:23 -0700
commit2a0efea1b8cef058268235321d17471aaf3d44ff (patch)
treee682dae491862bad9cb6ec2d500125cf987b51d8
parentfe078c7bdfc6a6a339c44a422bf5ca98130bf94a (diff)
downloadleetcode-2a0efea1b8cef058268235321d17471aaf3d44ff.tar.gz
leetcode-2a0efea1b8cef058268235321d17471aaf3d44ff.zip
2257. count unguarded cells in the grid
-rw-r--r--count_unguard_cells_grid.c84
-rw-r--r--count_unguard_cells_grid.py66
2 files changed, 150 insertions, 0 deletions
diff --git a/count_unguard_cells_grid.c b/count_unguard_cells_grid.c
new file mode 100644
index 0000000..17ad819
--- /dev/null
+++ b/count_unguard_cells_grid.c
@@ -0,0 +1,84 @@
+// 2257. Count Unguarded Cells in the Grid
+#include "leetcode.h"
+
+/*
+ * you are given two integers 'm' and 'n' representing a 0-indexed 'm x n' grid.
+ * you are also given two 2d integer arrays 'guards' and 'walls' where
+ * 'guards[i] = [row_i, col_i]' and 'walls[j] = [row_i, col_i]' represent the
+ * positions of the i'th guard and j'th wall respectively. a guard can see every
+ * cell in the four cardinal directions starting from their position unless
+ * obstructed by a wall or another guard. a cell is guarded if there is at least
+ * one guard that can see it. return the number of unoccupied cells that are not
+ * guarded.
+ */
+
+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--;
+ }
+ for (int i = 0; i < wallsSize; i++) {
+ grid[walls[i][0] * n + walls[i][1]] = 2;
+ unguarded--;
+ }
+ 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)
+ break;
+ if (!grid[row * n + c]) {
+ grid[row * n + c] = 3;
+ unguarded--;
+ }
+ }
+ for (int c = col - 1; c >= 0; c--) {
+ if (grid[row * n + c] == 1 || grid[row * n + c] == 2)
+ break;
+ if (!grid[row * n + c]) {
+ grid[row * n + c] = 3;
+ unguarded--;
+ }
+ }
+ for (int r = row + 1; r < m; r++) {
+ if (grid[r * n + col] == 1 || grid[r * n + col] == 2)
+ break;
+ if (!grid[r * n + col]) {
+ grid[r * n + col] = 3;
+ unguarded--;
+ }
+ }
+ for (int r = row - 1; r >= 0; r--) {
+ if (grid[r * n + col] == 1 || grid[r * n + col] == 2)
+ break;
+ if (!grid[r * n + col]) {
+ grid[r * n + col] = 3;
+ unguarded--;
+ }
+ }
+ }
+ free(grid);
+ return unguarded;
+}
+
+int main() {
+ int g1i[3][2] = {{0, 0}, {1, 1}, {2, 3}},
+ w1i[3][2] = {{0, 1}, {2, 2}, {1, 4}};
+ int g2i[1][2] = {{1, 1}}, w2i[4][2] = {{0, 1}, {1, 0}, {2, 1}, {1, 2}};
+ struct two_d_arr g1, w1, g2, w2;
+ two_d_arr_init(&g1, 3, 2, g1i);
+ two_d_arr_init(&w1, 3, 2, w1i);
+ two_d_arr_init(&g2, 1, 2, g2i);
+ two_d_arr_init(&w2, 4, 2, w2i);
+ printf("%d\n", countUnguarded(4, 6, g1.arr, g1.row_size, g1.col_size, w1.arr,
+ w1.row_size, w1.col_size)); // expect: 7
+ printf("%d\n", countUnguarded(3, 3, g2.arr, g2.row_size, g2.col_size, w2.arr,
+ w2.row_size, w2.col_size)); // expect: 4
+ two_d_arr_free(&g1);
+ two_d_arr_free(&g2);
+ two_d_arr_free(&w1);
+ two_d_arr_free(&w2);
+}
diff --git a/count_unguard_cells_grid.py b/count_unguard_cells_grid.py
new file mode 100644
index 0000000..1364dd3
--- /dev/null
+++ b/count_unguard_cells_grid.py
@@ -0,0 +1,66 @@
+# 2257. Count Unguarded Cells in the Grid
+
+"""
+you are given two integers 'm' and 'n' representing a 0-indexed 'm x n' grid.
+you are also given two 2d integer arrays 'guards' and 'walls' where
+'guards[i] = [row_i, col_i]' and 'walls[j] = [row_i, col_i]' represent the
+positions of the i'th guard and j'th wall respectively. a guard can see every
+cell in the four cardinal directions starting from their position unless
+obstructed by a wall or another guard. a cell is guarded if there is at least
+one guard that can see it. return the number of unoccupied cells that are not
+guarded.
+"""
+
+
+class Solution(object):
+ def countUnguarded(self, m, n, guards, walls):
+ """
+ :type m: int
+ :type n: int
+ :type guards: List[List[int]]
+ :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):
+ break
+ vis[i][col] = 1
+ for i in range(row - 1, -1, -1):
+ if vis[i][col] in (2, 3):
+ break
+ vis[i][col] = 1
+ for i in range(col + 1, n):
+ if vis[row][i] in (2, 3):
+ break
+ vis[row][i] = 1
+ for i in range(col - 1, -1, -1):
+ if vis[row][i] in (2, 3):
+ 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
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.countUnguarded(
+ m=4, n=6, guards=[[0, 0], [1, 1], [2, 3]], walls=[[0, 1], [2, 2], [1, 4]]
+ )
+ )
+ print(
+ obj.countUnguarded(
+ m=3, n=3, guards=[[1, 1]], walls=[[0, 1], [1, 0], [2, 1], [1, 2]]
+ )
+ )