Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2257.html
2257. Count Unguarded Cells in the Grid
- Difficulty: Medium.
- Related Topics: Array, Matrix, Simulation.
- Similar Questions: Bomb Enemy, Available Captures for Rook.
Problem
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] = [rowi, coli]
and walls[j] = [rowj, colj]
represent the positions of the ith
guard and jth
wall respectively.
A guard can see every cell in the four cardinal directions (north, east, south, or west) 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.**
Example 1:
Input: m = 4, n = 6, guards = [[0,0],[1,1],[2,3]], walls = [[0,1],[2,2],[1,4]]
Output: 7
Explanation: The guarded and unguarded cells are shown in red and green respectively in the above diagram.
There are a total of 7 unguarded cells, so we return 7.
Example 2:
Input: m = 3, n = 3, guards = [[1,1]], walls = [[0,1],[1,0],[2,1],[1,2]]
Output: 4
Explanation: The unguarded cells are shown in green in the above diagram.
There are a total of 4 unguarded cells, so we return 4.
Constraints:
-
1 <= m, n <= 105
-
2 <= m * n <= 105
-
1 <= guards.length, walls.length <= 5 * 104
-
2 <= guards.length + walls.length <= m * n
-
guards[i].length == walls[j].length == 2
-
0 <= rowi, rowj < m
-
0 <= coli, colj < n
-
All the positions in
guards
andwalls
are unique.
Solution (Java, C++, Python)
-
class Solution { public int countUnguarded(int m, int n, int[][] guards, int[][] walls) { char[][] matrix = new char[m][n]; int result = 0; for (int i = 0; i <= guards.length - 1; i++) { int guardRow = guards[i][0]; int guardCol = guards[i][1]; matrix[guardRow][guardCol] = 'G'; } for (int i = 0; i <= walls.length - 1; i++) { int wallRow = walls[i][0]; int wallCol = walls[i][1]; matrix[wallRow][wallCol] = 'W'; } for (int i = 0; i <= guards.length - 1; i++) { int currentRow = guards[i][0]; int currentCol = guards[i][1] - 1; while (currentCol >= 0) { if (matrix[currentRow][currentCol] != 'W' && matrix[currentRow][currentCol] != 'G') { matrix[currentRow][currentCol] = 'R'; } else { break; } currentCol--; } currentRow = guards[i][0]; currentCol = guards[i][1] + 1; while (currentCol <= n - 1) { if (matrix[currentRow][currentCol] != 'W' && matrix[currentRow][currentCol] != 'G') { matrix[currentRow][currentCol] = 'R'; } else { break; } currentCol++; } currentRow = guards[i][0] - 1; currentCol = guards[i][1]; while (currentRow >= 0) { if (matrix[currentRow][currentCol] != 'W' && matrix[currentRow][currentCol] != 'G') { matrix[currentRow][currentCol] = 'R'; } else { break; } currentRow--; } currentRow = guards[i][0] + 1; currentCol = guards[i][1]; while (currentRow <= m - 1) { if (matrix[currentRow][currentCol] != 'W' && matrix[currentRow][currentCol] != 'G') { matrix[currentRow][currentCol] = 'R'; } else { break; } currentRow++; } } for (int i = 0; i <= m - 1; i++) { for (int j = 0; j <= n - 1; j++) { if (matrix[i][j] != 'R' && matrix[i][j] != 'G' && matrix[i][j] != 'W') { result++; } } } return result; } }
-
Todo
-
class Solution: def countUnguarded( self, m: int, n: int, guards: List[List[int]], walls: List[List[int]] ) -> int: g = [[None] * n for _ in range(m)] for r, c in guards: g[r][c] = 'g' for r, c in walls: g[r][c] = 'w' for i, j in guards: for a, b in [[0, -1], [0, 1], [1, 0], [-1, 0]]: x, y = i, j while ( 0 <= x + a < m and 0 <= y + b < n and g[x + a][y + b] != 'w' and g[x + a][y + b] != 'g' ): x, y = x + a, y + b g[x][y] = 'v' return sum(not v for row in g for v in row) ############ # 2257. Count Unguarded Cells in the Grid # https://leetcode.com/problems/count-unguarded-cells-in-the-grid class Solution: def countUnguarded(self, rows: int, cols: int, guards: List[List[int]], walls: List[List[int]]) -> int: grid = [[1] * cols for _ in range(rows)] for x, y in walls: grid[x][y] = -1 def goLeft(x, y): dy = y - 1 while dy >= 0 and grid[x][dy] != 2 and grid[x][dy] != -1: grid[x][dy] = 2 dy -= 1 def goRight(x, y): dy = y + 1 while dy < cols and grid[x][dy] != 3 and grid[x][dy] != -1: grid[x][dy] = 3 dy += 1 def goTop(x, y): dx = x - 1 while dx >= 0 and grid[dx][y] != 4 and grid[dx][y] != -1: grid[dx][y] = 4 dx -= 1 def goBottom(x, y): dx = x + 1 while dx < rows and grid[dx][y] != 5 and grid[dx][y] != -1: grid[dx][y] = 5 dx += 1 guards.sort(key = lambda x : (-x[1], x[0])) for x, y in guards: goLeft(x, y) guards.sort(key = lambda x : (x[1], x[0])) for x, y in guards: goRight(x, y) guards.sort(key = lambda x : (-x[0], x[1])) for x, y in guards: goTop(x, y) guards.sort(key = lambda x : (x[0], x[1])) for x, y in guards: goBottom(x, y) for x, y in guards: grid[x][y] = -1 res = 0 for x in range(rows): for y in range(cols): if grid[x][y] == 1: res += 1 return res
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).