Leetcode 2257: Count Unguarded Cells in the Grid
You are given a 0-indexed grid of size
m x n. Some cells in the grid are occupied by guards, and some by walls. A guard can observe all cells in the four cardinal directions (north, east, south, and west) from its position unless blocked by a wall or another guard. A cell is considered guarded if at least one guard can see it. Your task is to determine the number of cells that are unoccupied and are not guarded.Problem
Approach
Steps
Complexity
Input: The input consists of the grid dimensions `m` and `n`, followed by two lists: `guards` and `walls`. The `guards` list contains the positions of guards, and the `walls` list contains the positions of walls in the grid.
Example: m = 5, n = 5, guards = [[0,0],[2,2],[4,4]], walls = [[1,1],[3,3]]
Constraints:
• 1 <= m, n <= 10^5
• 2 <= m * n <= 10^5
• 1 <= guards.length, walls.length <= 5 * 10^4
• 2 <= guards.length + walls.length <= m * n
• guards[i].length == walls[j].length == 2
• 0 <= rowi, rowj < m
• 0 <= coli, colj < n
• All positions in guards and walls are unique.
Output: Return the number of unoccupied and unguarded cells in the grid.
Example: Output: 12
Constraints:
Goal: To count the number of cells that are neither occupied by walls nor guarded by any guard.
Steps:
• Initialize a grid of size `m x n` with all values set to 0 (indicating unoccupied and unguarded cells).
• Mark the cells occupied by walls with a 1.
• Mark the cells occupied by guards with a 3.
• For each guard, mark the cells in the four cardinal directions (north, south, east, and west) as guarded, until a wall or another guard is encountered.
• After processing all guards, count the number of cells that are neither occupied by walls nor guarded.
Goal: Ensure that the solution handles large grid sizes and a significant number of guards and walls efficiently.
Steps:
• The grid size can be very large (up to 10^5), so an efficient solution is required.
• Handle cases where there are no guards or no walls.
Assumptions:
• Each guard can only guard cells in the four cardinal directions, and no diagonal observation is allowed.
• If a guard is at a position, it is not considered unguarded by itself.
• Input: m = 5, n = 5, guards = [[0,0],[2,2],[4,4]], walls = [[1,1],[3,3]]
• Explanation: The guards will guard cells in the four cardinal directions unless blocked by a wall. After processing the guards and walls, the remaining unguarded and unoccupied cells are counted.
• Input: m = 4, n = 4, guards = [[0,0]], walls = [[1,1], [3,3]]
• Explanation: The grid has walls at (1,1) and (3,3), and a guard at (0,0). After marking the guarded cells, we count the unguarded ones.
Approach: The problem can be solved efficiently by using a grid to keep track of the state of each cell and iterating through each guard to mark the cells they can observe.
Observations:
• Each guard can influence a significant number of cells, so the solution needs to efficiently track the influence of each guard.
• Walls block the guard's vision, so they need to be taken into account while marking guarded cells.
• We can use a grid to represent the state of each cell and iteratively mark the cells guarded by each guard. We can then count the unguarded cells.
Steps:
• Create a grid to represent the m x n grid.
• Iterate over each wall and mark the corresponding cells in the grid.
• Iterate over each guard and mark the cells in all four directions as guarded, stopping at walls or other guards.
• Finally, count the unoccupied and unguarded cells in the grid and return the result.
Empty Inputs:
• If there are no guards, all cells except walls are unguarded.
Large Inputs:
• Ensure that the solution can handle grids with a large number of cells (up to 10^5) efficiently.
Special Values:
• If the grid is completely surrounded by walls or contains no guards, the number of unguarded cells is easy to determine.
Constraints:
• Handle large inputs efficiently by processing guards and walls in an optimized manner.
int countUnguarded(int m, int n, vector<vector<int>>& guards, vector<vector<int>>& walls) {
vector<vector<int>> grid(m, vector<int>(n, 0));
for(auto it: walls) {
grid[it[0]][it[1]] = 1;
}
for(auto it: guards) {
grid[it[0]][it[1]] = 3;
}
for(auto it: guards) {
int x = it[0], y = it[1];
for(int i = y + 1; i < n && grid[x][i] != 1 && grid[x][i] != 3; i++) {
grid[x][i] = 2;
}
for(int i = y - 1; i >=0 && grid[x][i] != 1 && grid[x][i] != 3; i--) {
grid[x][i] = 2;
}
for(int i = x + 1; i < m && grid[i][y] != 1 && grid[i][y] != 3; i++) {
grid[i][y] = 2;
}
for(int i = x - 1; i >= 0 && grid[i][y] != 1 && grid[i][y] != 3; i--) {
grid[i][y] = 2;
}
// grid[x][y] = 3;
}
int cnt = 0;
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
if(grid[i][j] == 0) cnt++;
return cnt;
}
1 : Function Declaration
int countUnguarded(int m, int n, vector<vector<int>>& guards, vector<vector<int>>& walls) {
This is the function signature where the input parameters `m` and `n` represent the dimensions of the grid, while `guards` and `walls` represent the locations of the guards and walls, respectively.
2 : Grid Initialization
vector<vector<int>> grid(m, vector<int>(n, 0));
Here, we create a grid with `m` rows and `n` columns, initializing all values to 0, representing empty cells.
3 : Walls Placement
for(auto it: walls) {
This loop iterates through the walls' positions and marks them on the grid.
4 : Mark Walls
grid[it[0]][it[1]] = 1;
Each wall's position is marked with a value of 1 on the grid, indicating that the cell is blocked.
5 : Guards Placement
for(auto it: guards) {
This loop iterates through the guards' positions and places them on the grid.
6 : Mark Guards
grid[it[0]][it[1]] = 3;
Each guard's position is marked with a value of 3 on the grid.
7 : Guard Influence Calculation
for(auto it: guards) {
This loop processes each guard's position to mark all cells in its line of sight as guarded.
8 : Get Guard Coordinates
int x = it[0], y = it[1];
Here, we extract the coordinates `x` and `y` of the current guard.
9 : Guard Influence Right
for(int i = y + 1; i < n && grid[x][i] != 1 && grid[x][i] != 3; i++) {
This loop marks cells to the right of the guard as being in its line of sight, stopping at walls or other guards.
10 : Mark Right Influence
grid[x][i] = 2;
Each cell in the guard's rightward line of sight is marked with a 2 to indicate it is under guard surveillance.
11 : Guard Influence Left
for(int i = y - 1; i >= 0 && grid[x][i] != 1 && grid[x][i] != 3; i--) {
This loop marks cells to the left of the guard as being in its line of sight.
12 : Mark Left Influence
grid[x][i] = 2;
Each cell in the guard's leftward line of sight is marked with a 2 to indicate it is under guard surveillance.
13 : Guard Influence Down
for(int i = x + 1; i < m && grid[i][y] != 1 && grid[i][y] != 3; i++) {
This loop marks cells below the guard as being in its line of sight.
14 : Mark Down Influence
grid[i][y] = 2;
Each cell in the guard's downward line of sight is marked with a 2.
15 : Guard Influence Up
for(int i = x - 1; i >= 0 && grid[i][y] != 1 && grid[i][y] != 3; i--) {
This loop marks cells above the guard as being in its line of sight.
16 : Mark Up Influence
grid[i][y] = 2;
Each cell in the guard's upward line of sight is marked with a 2.
17 : Count Unguarded Cells
int cnt = 0;
We initialize a counter `cnt` to track the number of unguarded cells.
18 : Iterate Grid
for(int i = 0; i < m; i++)
This loop iterates through each row of the grid.
19 : Iterate Grid Columns
for(int j = 0; j < n; j++)
This loop iterates through each column of the grid.
20 : Count Unguarded Cells
if(grid[i][j] == 0) cnt++;
If the cell is not a wall (1) or a guard (3), we increment the counter for unguarded cells.
21 : Return Count
return cnt;
Finally, the function returns the count of unguarded cells.
Best Case: O(m * n)
Average Case: O(m * n)
Worst Case: O(m * n)
Description: The time complexity is linear in terms of the number of cells in the grid, as we process each guard and wall individually.
Best Case: O(m * n)
Worst Case: O(m * n)
Description: The space complexity is proportional to the size of the grid, as we store the state of each cell.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus