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.
1#include <vector>
2using namespace std;
3
4int countUnguarded(int m, int n, vector<vector<int>>& guards, vector<vector<int>>& walls) {
5 vector<vector<int>> grid(m, vector<int>(n, 0));
6 for (auto& w : walls) grid[w[0]][w[1]] = -1;
7 for (auto& g : guards) grid[g[0]][g[1]] = -2;
8
9 int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
10
11 auto guard_area = [&](int x, int y) {
12 for (auto& d : directions) {
13 int nx = x + d[0], ny = y + d[1];
14 while (nx >= 0 && ny >= 0 && nx < m && ny < n && grid[nx][ny] != -1 && grid[nx][ny] != -2) {
15 if (grid[nx][ny] == 0) grid[nx][ny] = 1;
16 nx += d[0]; ny += d[1];
17 }
18 }
19 };
20
21 for (auto& g : guards) guard_area(g[0], g[1]);
22
23 int unguarded_count = 0;
24 for (auto& row : grid)
25 for (int cell : row)
26 if (cell == 0) unguarded_count++;
27
28 return unguarded_count;
29}This C++ implementation mirrors the Python strategy: mark walls, extend guard view using a loop over packet direction. After setting areas, count default state cells (0s) for unguarded total.
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.