Count Unguarded Cells in the Grid

An m by n grid uses zero-based row and column coordinates. The arrays guards and walls list occupied cells as [row, column] pairs. All listed positions are distinct.

Each guard watches along its row and column in all four directions. Its view stops at the grid boundary, a wall, or another guard. A cell is watched if at least one guard can see it.

Return the number of empty cells that no guard can see. Cells containing guards or walls are not counted.

In the diagrams, G marks a guard, a solid square marks a wall, and diagonal hatching marks watched cells.

Example 1:

Input: m = 1
n = 6
guards = [[0,0]]
walls = [[0,3]]

Output: 2

Explanation: The guard watches columns 1 and 2. The wall at column 3 blocks its view, so the empty cells at columns 4 and 5 are unguarded.

Example 2:

Input: m = 4
n = 1
guards = [[1,0]]
walls = [[2,0]]

Output: 1

Explanation: The guard watches row 0. The wall at row 2 blocks its view downward, leaving the empty cell at row 3 unguarded.

Example 3:

Input: m = 3
n = 3
guards = [[0,0]]
walls = [[1,1]]

Output: 3

Explanation: The guard watches the rest of row 0 and column 0. The wall occupies [1,1]. The three remaining empty cells, [1,2], [2,1], and [2,2], are unguarded.

Constraints:

• 1 <= m, n <= 100000
• 2 <= m × n <= 100000
• 1 <= guards.length, walls.length <= 50000
• 2 <= guards.length + walls.length <= m × n
• Every position is a pair [row, column] with 0 <= row < m and 0 <= column < n.
• All positions in guards and walls are distinct.

Topics

Array Matrix Simulation

Company Tags

Please upgrade to NeetCode Pro to view company tags.