aboutsummaryrefslogtreecommitdiff
path: root/count_unguard_cells_grid.c
diff options
context:
space:
mode:
Diffstat (limited to 'count_unguard_cells_grid.c')
-rw-r--r--count_unguard_cells_grid.c84
1 files changed, 84 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);
+}