diff options
Diffstat (limited to 'count_unguard_cells_grid.c')
-rw-r--r-- | count_unguard_cells_grid.c | 84 |
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); +} |