diff options
author | Jack Sangdahl <[email protected]> | 2024-11-21 12:14:23 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-11-21 12:14:23 -0700 |
commit | 2a0efea1b8cef058268235321d17471aaf3d44ff (patch) | |
tree | e682dae491862bad9cb6ec2d500125cf987b51d8 | |
parent | fe078c7bdfc6a6a339c44a422bf5ca98130bf94a (diff) | |
download | leetcode-2a0efea1b8cef058268235321d17471aaf3d44ff.tar.gz leetcode-2a0efea1b8cef058268235321d17471aaf3d44ff.zip |
2257. count unguarded cells in the grid
-rw-r--r-- | count_unguard_cells_grid.c | 84 | ||||
-rw-r--r-- | count_unguard_cells_grid.py | 66 |
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]] + ) + ) |