Problem Statement

You are given an m × n grid with some cells designated as walls, some as guards, and others as empty cells. A guard can protect all empty cells in its row and column until its vision is blocked by a wall or another guard. The task is to determine how many cells remain unguarded (not protected by any guard) in the grid.

Note: A guard's protection does not extend past a wall or another guard. In other words, if a wall or another guard is encountered in a particular direction, the guard cannot protect any cells beyond that point in that direction.

Examples

Example 1

Input:

m = 4, n = 6
walls = [[0,1],[2,3],[1,4]]
guards = [[0,0],[1,1],[2,2]]

Output:

7

Explanation: In the 4×6 grid, guards protect cells in their rows and columns until a wall or another guard blocks the way. The final grid (marking guarded cells) would look like this:

• G = Guard
• W = Wall
• * = Guarded cell (protected by at least one guard)
• U = Unguarded empty cell

In this configuration, there are 7 cells labeled U that remain unguarded.

Example 2

Input:

m = 3, n = 3
walls = [[1,1]]
guards = [[0,1],[1,0],[2,2]]

Output:

4

Explanation: The walls block some of the guards' lines of sight. Despite multiple guards, certain empty cells are not reachable by any guard's protection due to the wall at (1,1). These cells remain unprotected. The final grid marking guarded vs. unguarded might be visualized as:

• G = Guard, W = Wall, * = Guarded, U = Unguarded

Here, 4 cells are unguarded (marked U). The wall at (1,1) prevents the guards from seeing certain cells (for example, the guard at (0,1) cannot see cells below the wall, and the guard at (1,0) cannot see cells to the right of the wall).

Hints

1. A guard protects in all four directions (up, down, left, right) but its view is blocked by walls or other guards.
2. Start by marking the positions of all guards and walls on the grid.
3. Then, for each guard, simulate its vision along each of the four directions until a wall or another guard blocks the path.
4. Finally, count the empty cells that remain unguarded.

Approach 1: Brute Force Simulation

Idea

We can simulate the process directly. First, mark all guard and wall positions on the grid. Then, for each guard, traverse in each of the four directions (left, right, up, and down), marking every reachable empty cell as guarded until you hit a wall or another guard. After processing all guards, any empty cell that was never marked is unguarded. This brute-force simulation is straightforward given the grid size constraints.

Why this works: Each guard independently covers its line of sight. By marking out all cells visible to any guard, we ensure that we correctly identify which cells are protected. In the end, cells that remain unmarked are those not visible to any guard (i.e., truly unguarded).

Algorithm (Step-by-Step)

1. Initialize the grid representation: Create an m x n grid data structure (e.g., a 2D list) to represent the state of each cell. Mark empty cells with 0. Then mark guard positions with a special value (e.g., 1) and wall positions with another value (e.g., -1). This helps differentiate between guards, walls, and empties.
2. Mark guards' vision: For each guard in the grid, simulate its line of sight in the four directions:

   • Upwards: move step by step in the same column, decreasing the row index until you go out of bounds or hit a cell that is a wall or another guard. Mark each encountered empty cell as guarded (for example, set its value to 2 to denote "guarded"). Stop when a wall or guard is encountered.

   • Downwards: move downward (increasing row index) in the same column, stopping at walls/guards or grid boundaries, marking empties as guarded.

   • Left: move left in the same row (decreasing column index), similarly stopping at walls or another guard.

   • Right: move right in the same row (increasing column index) with the same stopping condition.

3. Count unguarded cells: After processing all guards, iterate through the grid and count how many cells remain empty and unmarked (still 0 in our representation). These are the cells not protected by any guard.
4. Return the count of unguarded cells.

During this simulation, a guard or wall will effectively block further traversal in that direction. We do not mark wall cells or guard cells as "guarded" (and we exclude them from counting), since the problem is only concerned with empty cells that are guarded or unguarded.

Complexity Analysis

• Time Complexity: Marking the initial positions of walls and guards takes O(m×n) in the worst case (covering the whole grid). Then for each guard, we might traverse up to O(m) cells vertically and O(n) cells horizontally in the worst case. If there are G guards, the worst-case time is about O(m × n + G × (m + n)). In the worst scenario where every cell has a guard (except walls), this is O(m×n + m×n) = O(m×n). Given the constraints (m, n ≤ 100), this brute-force approach is efficient enough.

• Space Complexity: O(m × n) for the grid representation. Aside from the grid, we only use a few counters and indices, so auxiliary space is minimal. This fits within typical memory limits easily.

Implementation

Below are implementations of the above approach in both Python and Java for clarity:

Python Implementation

Java Implementation

Common Mistakes

• Not stopping at guards/walls: A frequent mistake is forgetting to stop the guard’s scanning when another guard is encountered. Remember that a guard also acts as an obstacle for another guard's vision (just like a wall).

• Counting guards or walls as "unguarded": Only empty cells should be counted as unguarded. Make sure that guard cells and wall cells are never counted in the final tally.

• Out-of-bounds errors: When scanning in a direction, it's easy to run off the grid edges. Ensure your loop conditions prevent indexing outside the grid bounds.

• Marking already guarded cells incorrectly: In the simulation, once a cell is marked guarded by one guard, another guard’s simulation should treat that cell as non-empty (to stop further traversal if encountered). The approach above handles this by marking guarded cells with a distinct value (2), so another guard will not continue past that cell. Not handling this can either cause redundant work or incorrect continuation beyond an already guarded cell (though logically it wouldn't change the final count, it could affect performance or the traversal logic).

Edge Cases

Consider the following edge scenarios to ensure the solution handles them correctly:

• No guards at all: If there are zero guards, then none of the empty cells get protected. The number of unguarded cells would just be all the empty cells (which is total cells minus any walls). For example, if guards = [], every empty cell is unguarded.

• No walls: If there are no walls, guards will have an unobstructed view along their entire row and column. The only empty cells that remain unguarded would be those that happen to not lie in any guard's row or column. If guards cover all rows and columns, then potentially no cell remains unguarded.

• Guards adjacent to each other: If two guards are in the same row or column with no wall between them, they block each other’s view beyond their position. For instance, if two guards are in the same row, each guard can see up to the other guard's cell but not past it. Cells lying beyond one guard in line of sight of the other will remain unguarded because the guard in between acts as a barrier.

• All cells are walls or guards: If every cell is either a wall or a guard (no empty cell at all), then trivially, the number of unguarded cells is 0 (since there are no empty cells to begin with).

• Grid boundaries: Guards at the edges of the grid only scan inward (since outside the grid is effectively a boundary). Ensure that the algorithm correctly handles guards on the perimeter without going out of range.

By testing these edge cases, you can be confident that the solution works for all scenarios within the problem’s constraints.

Related Problems

This problem is essentially a grid simulation with obstacles, and it’s related to other problems involving grids, obstacles, and range of effect:

• Walls and Gates (LeetCode 286): In that problem, you fill each empty room in a grid with the distance to its nearest gate, considering walls as obstacles. It similarly uses the concept of walls blocking movement, and one can use multi-source BFS from all gates at once. The notion of walls partitioning the grid is common to both problems.

• Grid Illumination (LeetCode 1001): This is a problem where lamps illuminate their row, column, and diagonals. There are no walls in that scenario, but it’s a related idea of certain cells affecting others in straight lines. The difference is that illumination is not blocked by obstacles in that problem, whereas in our guards problem, walls (and other guards) block the "illumination" (guard vision).

• Matrix Bordering Problems: There are various grid problems like Surrounded Regions or Flood Fill which, while not about guards, involve scanning a grid with stopping conditions. They build similar intuition about how to traverse or influence neighboring cells under certain constraints.