Count Unguarded Cells in the Grid

medium array matrix simulation

Problem

You have an m × n grid with some cells holding guards and others holding walls. A guard sees every cell in the four cardinal directions (north, east, south, west) from its position until a wall or another guard blocks the line of sight. A cell is guarded if at least one guard can see it. Return the number of unoccupied cells that are not guarded.

Inputm = 4, n = 6, guards = [[0,0],[1,1],[2,3]], walls = [[0,1],[2,2],[1,4]]

Output7

After every guard projects its sight lines, 7 unoccupied cells remain unseen.

Inputm = 3, n = 3, guards = [[1,1]], walls = [[0,1],[1,0],[2,1],[1,2]]

Output4

Walls box the single guard in on all four sides, so the 4 corner cells stay unguarded.

m (rows)

n (cols)

guards (r:c, comma-separated)

walls (r:c, comma-separated)

def count_unguarded(m, n, guards, walls):
    EMPTY, SEEN, GUARD, WALL = 0, 1, 2, 3
    g = [[EMPTY] * n for _ in range(m)]
    for r, c in walls:
        g[r][c] = WALL
    for r, c in guards:
        g[r][c] = GUARD
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    for r, c in guards:
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            while 0 <= nr < m and 0 <= nc < n and g[nr][nc] < GUARD:
                if g[nr][nc] == EMPTY:
                    g[nr][nc] = SEEN
                nr, nc = nr + dr, nc + dc
    return sum(cell == EMPTY for row in g for cell in row)

function countUnguarded(m, n, guards, walls) {
  const EMPTY = 0, SEEN = 1, GUARD = 2, WALL = 3;
  const g = Array.from({ length: m }, () => new Array(n).fill(EMPTY));
  for (const [r, c] of walls) g[r][c] = WALL;
  for (const [r, c] of guards) g[r][c] = GUARD;
  const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  for (const [r, c] of guards) {
    for (const [dr, dc] of dirs) {
      let nr = r + dr, nc = c + dc;
      while (nr >= 0 && nr < m && nc >= 0 && nc < n && g[nr][nc] < GUARD) {
        if (g[nr][nc] === EMPTY) g[nr][nc] = SEEN;
        nr += dr; nc += dc;
      }
    }
  }
  let count = 0;
  for (const row of g) for (const cell of row) if (cell === EMPTY) count++;
  return count;
}

int countUnguarded(int m, int n, int[][] guards, int[][] walls) {
    final int EMPTY = 0, SEEN = 1, GUARD = 2, WALL = 3;
    int[][] g = new int[m][n];
    for (int[] w : walls) g[w[0]][w[1]] = WALL;
    for (int[] gu : guards) g[gu[0]][gu[1]] = GUARD;
    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    for (int[] gu : guards) {
        for (int[] d : dirs) {
            int nr = gu[0] + d[0], nc = gu[1] + d[1];
            while (nr >= 0 && nr < m && nc >= 0 && nc < n && g[nr][nc] < GUARD) {
                if (g[nr][nc] == EMPTY) g[nr][nc] = SEEN;
                nr += d[0]; nc += d[1];
            }
        }
    }
    int count = 0;
    for (int[] row : g) for (int cell : row) if (cell == EMPTY) count++;
    return count;
}

int countUnguarded(int m, int n, vector<vector<int>>& guards, vector<vector<int>>& walls) {
    const int EMPTY = 0, SEEN = 1, GUARD = 2, WALL = 3;
    vector<vector<int>> g(m, vector<int>(n, EMPTY));
    for (auto& w : walls) g[w[0]][w[1]] = WALL;
    for (auto& gu : guards) g[gu[0]][gu[1]] = GUARD;
    int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    for (auto& gu : guards) {
        for (auto& d : dirs) {
            int nr = gu[0] + d[0], nc = gu[1] + d[1];
            while (nr >= 0 && nr < m && nc >= 0 && nc < n && g[nr][nc] < GUARD) {
                if (g[nr][nc] == EMPTY) g[nr][nc] = SEEN;
                nr += d[0]; nc += d[1];
            }
        }
    }
    int count = 0;
    for (auto& row : g) for (int cell : row) if (cell == EMPTY) count++;
    return count;
}

Explanation

This is a grid marking problem solved by direct simulation. Each cell holds one of four labels: EMPTY, GUARD, WALL, or SEEN (an empty cell that some guard can already see).

We first stamp every wall and every guard into the grid. Order matters only in that both occupy cells; we keep WALL and GUARD as distinct blockers because a guard's line of sight stops at either one.

The label values are ordered EMPTY = 0, SEEN = 1, GUARD = 2, WALL = 3 on purpose: the two blockers (GUARD, WALL) are the largest, so a single test label < GUARD means "passable" — true for EMPTY and SEEN, false for a guard or a wall.

Then, for each guard, we cast a ray in all four cardinal directions. A ray walks one cell at a time: while the next cell is inside the grid and is passable (label < GUARD), we mark any still-EMPTY cell as SEEN and advance. The moment we step out of bounds or reach a GUARD/WALL, that ray stops.

Because SEEN is below GUARD, a cell already lit by an earlier guard does not block a later guard's ray — only guards and walls do. We only flip cells that are still EMPTY, so overlapping sight lines from different guards cost nothing extra.

Finally we sweep the whole grid and count the cells still labelled EMPTY: those are the unoccupied, unguarded cells. Each cell is touched a constant number of times per direction, giving linear time in the grid size.

Time: O(m · n) Space: O(m · n)