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 /count_unguard_cells_grid.py | |
parent | fe078c7bdfc6a6a339c44a422bf5ca98130bf94a (diff) | |
download | leetcode-2a0efea1b8cef058268235321d17471aaf3d44ff.tar.gz leetcode-2a0efea1b8cef058268235321d17471aaf3d44ff.zip |
2257. count unguarded cells in the grid
Diffstat (limited to 'count_unguard_cells_grid.py')
-rw-r--r-- | count_unguard_cells_grid.py | 66 |
1 files changed, 66 insertions, 0 deletions
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]] + ) + ) |