Problem

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.

Examples

Example 1:

$$ \begin{array}{|c|c|c|c|c|c|} \hline G & W & \colorbox{green}{} & \colorbox{red}{} & \colorbox{green}{} & \colorbox{green}{} \\ \hline \colorbox{red}{} & G & \colorbox{red}{} & \colorbox{red}{} & W & \colorbox{green}{} \\ \hline \colorbox{red}{} & \colorbox{red}{} & W & G & \colorbox{red}{} & \colorbox{red}{} \\ \hline \colorbox{red}{} & \colorbox{red}{} & \colorbox{green}{} & \colorbox{red}{} & \colorbox{green}{} & \colorbox{green}{} \\ \hline \end{array} $$

1
2
3
4

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:

$$ \begin{array}{|c|c|c|} \hline \colorbox{green}{\ \ \ \ } & W & \colorbox{green}{\ \ \ \ } \\ \hline W & G & W \\ \hline \colorbox{green}{\ \ \ \ } & W & \colorbox{green}{\ \ \ \ } \\ \hline \end{array} $$

1
2
3
4

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.

Solution

Method 1 - DFS

To determine the count of unoccupied cells that are not guarded in an m x n grid given the positions of guards and walls.

Here are the steps:

  1. Initialize the Grid:
    • Create an m x n grid initialized with zeros. Each cell in this grid can have one of the following states:
      • 0: Free
      • 1: Guard
      • 2: Wall
      • 3: Guarded
  2. Mark Guards and Walls:
    • Update the grid based on the positions of guards (marking these cells as 1).
    • Update the grid based on the positions of walls (marking these cells as 2).
  3. Guard the Cells:
    • For each guard, mark the cells that the guard can see in the four cardinal directions (north, south, east, and west).
    • While marking, stop if you encounter another guard (1) or a wall (2).
  4. Count the Unguarded Cells:
    • Iterate through the grid and count the cells that are free (0).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

class Solution {
    public int countUnguarded(int m, int n, int[][] guards, int[][] walls) {
        int[][] grid = new int[m][n];
        // 0 = free, 1 = guard, 2 = wall, 3 = guarded

        for (int[] guard : guards) {
            grid[guard[0]][guard[1]] = 1;
        }
        for (int[] wall : walls) {
            grid[wall[0]][wall[1]] = 2;
        }

        for (int[] guard : guards) {
            markGuarded(grid, guard[0], guard[1], m, n);
        }

        int res = 0;
        for (int[] row : grid) {
            for (int cell : row) {
                if (cell == 0) {
                    res++;
                }
            }
        }

        return res;
    }

    private void markGuarded(int[][] grid, int r, int c, int m, int n) {
        for (int row = r + 1; row < m; row++) {
            if (grid[row][c] == 1 || grid[row][c] == 2) break;
            grid[row][c] = 3;
        }
        for (int row = r - 1; row >= 0; row--) {
            if (grid[row][c] == 1 || grid[row][c] == 2) break;
            grid[row][c] = 3;
        }
        for (int col = c + 1; col < n; col++) {
            if (grid[r][col] == 1 || grid[r][col] == 2) break;
            grid[r][col] = 3;
        }
        for (int col = c - 1; col >= 0; col--) {
            if (grid[r][col] == 1 || grid[r][col] == 2) break;
            grid[r][col] = 3;
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution:
    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:
        grid: List[List[int]] = [[0] * n for _ in range(m)]
        # 0 = free, 1 = guard, 2 = wall, 3 = guarded

        for guard in guards:
            grid[guard[0]][guard[1]] = 1
        for wall in walls:
            grid[wall[0]][wall[1]] = 2

        for guard in guards:
            self.mark_guarded(grid, guard[0], guard[1], m, n)
        
        res: int = 0
        for row in grid:
            for cell in row:
                if cell == 0:
                    res += 1
        
        return res

    def mark_guarded(self, grid: List[List[int]], r: int, c: int, m: int, n: int) -> None:
        for row in range(r + 1, m):
            if grid[row][c] == 1 or grid[row][c] == 2:
                break
            grid[row][c] = 3
        for row in range(r - 1, -1, -1):
            if grid[row][c] == 1 or grid[row][c] == 2:
                break
            grid[row][c] = 3
        for col in range(c + 1, n):
            if grid[r][col] == 1 or grid[r][col] == 2:
                break
            grid[r][col] = 3
        for col in range(c - 1, -1, -1):
            if grid[r][col] == 1 or grid[r][col] == 2:
                break
            grid[r][col] = 3

Complexity

  • ⏰ Time complexity: O(m * n)
    • Initializing the grid and marking guards and walls takes O(m * n).
    • Marking the guarded cells for each guard might visit each cell in the grid, resulting in O(m * n) time.
    • Counting the unguarded cells takes O(m * n).
  • 🧺 Space complexity: O(m * n) as we use an additional grid of size m x n to track the state of each cell.