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.
1class Solution {
2 public int countUnguarded(int m, int n, int[][] guards, int[][] walls) {
3 int[][] grid = new int[m][n];
4 for (int[] wall : walls) grid[wall[0]][wall[1]] = -1;
5 for (int[] guard : guards) grid[guard[0]][guard[1]] = -2;
6
7 int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
8
9 var guardArea = (int x, int y) -> {
10 for (int[] dir : directions) {
11 int nx = x + dir[0], ny = y + dir[1];
12 while (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] != -1 && grid[nx][ny] != -2) {
13 if (grid[nx][ny] == 0) grid[nx][ny] = 1;
14 nx += dir[0]; ny += dir[1];
15 }
16 }
17 };
18
19 for (int[] guard : guards) guardArea.applyAsInt(guard[0], guard[1]);
20
21 int unguardedCount = 0;
22 for (int[] row : grid)
23 for (int cell : row)
24 if (cell == 0) unguardedCount++;
25
26 return unguardedCount;
27 }
28}In Java, we make use of lambda functions for grid searching and direction checking. Walls prevent passing and cells translate marked for guards for avoiding duplicates through visible paths.
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.