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);
}
|