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 <= 1052 <= m * n <= 1051 <= guards.length, walls.length <= 5 * 1042 <= guards.length + walls.length <= m * nguards[i].length == walls[j].length == 20 <= rowi, rowj < m0 <= coli, colj < nguards and walls are unique.This approach simulates how each guard covers the surrounding cells using a Breadth-First Search (BFS). Each guard's visibility direction (up, down, left, right) is explored until a wall or another guard is encountered. This is efficiently managed by marking cells on the grid as guarded when checked.
This Python solution initializes a grid where non-zero values denote walls and guards (-1 for walls, -2 for guards). Each guard initiates a BFS to mark accessible cells as 'guarded' (1). After setting up all guards, we count unguarded cells (still marked as 0).
JavaScript
C++
Java
Time Complexity: O(m * n + g + w), where g is the number of guards and w is the number of walls due to establishing the grid. Each BFS operation per guard affects linear paths on the grid. Space Complexity: O(m * n), due to the grid storage.
This method involves scanning the grid twice. The first pass evaluates each row and column to determine guard ocular coverage, interrupted by other guards or walls. The second pass counts cells still unmarked (unkempt).
This Python code initially fills the grid with walls and guards. Each line is scanned for unbroken visibility, updating guard effects directly, followed by a transpose to achieve column effects, before computing free cells.
JavaScript
Time Complexity: O(m * n), primarily from traversals of separated lines. Space Complexity: O(m * n), the redundancy of either process like transpose or count verification.
| Approach | Complexity |
|---|---|
| Approach 1: Breadth-First Search (BFS) for Guarding | Time Complexity: O(m * n + g + w), where g is the number of guards and w is the number of walls due to establishing the grid. Each BFS operation per guard affects linear paths on the grid. Space Complexity: O(m * n), due to the grid storage. |
| Approach 2: Two-Pass Grid Sweep | Time Complexity: O(m * n), primarily from traversals of separated lines. Space Complexity: O(m * n), the redundancy of either process like transpose or count verification. |
Count Unguarded Cells in the Grid - Leetcode 2257 - Python • NeetCodeIO • 8,112 views views
Watch 9 more video solutions →Practice Count Unguarded Cells in the Grid with our built-in code editor and test cases.
Practice on FleetCode