Sponsored
Sponsored
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.
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.
1from collections import deque
2
3def countUnguarded(m, n, guards, walls):
4 grid = [[0] * n for _ in range(m)]
5 for x, y in walls:
6 grid[x][y] = -1 # mark walls
7 for x, y in guards:
8 grid[x][y] = -2 # mark guards
9
10 directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] # right, down, left, up
11
12 def guard_area(x, y):
13 for dx, dy in directions:
14 nx, ny = x + dx, y + dy
15 while 0 <= nx < m and 0 <= ny < n and grid[nx][ny] != -1 and grid[nx][ny] != -2:
16 if grid[nx][ny] == 0:
17 grid[nx][ny] = 1 # mark as guarded
18 nx += dx
19 ny += dy
20
21 for x, y in guards:
22 guard_area(x, y)
23
24 unguarded_count = sum(row.count(0) for row in grid)
25 return unguarded_count
26This 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).
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).
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.
1function countUnguarded(m, n, guards, walls)
Using JavaScript, this solution evaluates each row and column separately through line passes. A mirroring of scans bases cell guard status to facilitate final calculations.