LeetCode 2257: Count Unguarded Cells in the Grid
Problem Description
Explanation:
To solve this problem, we need to determine the unguarded cells in the grid by considering the positions of guards and walls. We can achieve this by simulating the visibility of guards in the grid and marking the cells they can see. Finally, we count the unguarded cells that are not marked by any guard.
- Create a boolean grid to represent the visibility status of each cell.
- Iterate through the guards and mark the cells they can see in all four cardinal directions.
- Iterate through the walls and mark the cells they obstruct.
- Count the unguarded cells that are not marked by any guard.
Time Complexity: O(m * n + guards.length + walls.length) Space Complexity: O(m * n)
:
Solutions
class Solution {
public int countUnguardedCells(int m, int n, int[][] guards, int[][] walls) {
boolean[][] guarded = new boolean[m][n];
for (int[] guard : guards) {
int row = guard[0];
int col = guard[1];
markVisibleCells(row, col, m, n, guarded);
}
for (int[] wall : walls) {
int row = wall[0];
int col = wall[1];
guarded[row][col] = true;
}
int unguardedCount = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (!guarded[i][j]) {
unguardedCount++;
}
}
}
return unguardedCount;
}
private void markVisibleCells(int row, int col, int m, int n, boolean[][] guarded) {
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (int[] dir : directions) {
int newRow = row + dir[0];
int newCol = col + dir[1];
while (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n) {
guarded[newRow][newCol] = true;
newRow += dir[0];
newCol += dir[1];
}
}
}
}Loading editor...