aboutsummaryrefslogtreecommitdiff
path: root/count_unguard_cells_grid.c
blob: 17ad819514e7431bd5b850e49e5cc7844f00f094 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
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);
}