We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Unguarded Cells in the Grid

Difficulty: Medium

Problem Description

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] = [row_i, col_i] and walls[j] = [row_j, col_j] represent the positions of the i-th guard and j-th 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.

Key Insights

  • Guards can see in four directions until they are blocked by walls or other guards.
  • Cells occupied by guards or walls are not counted as unguarded cells.
  • We need to efficiently track which cells are guarded based on the positions of guards and walls.

Space and Time Complexity

Time Complexity: O(m * n) - in the worst case, we may need to check each cell in the grid. Space Complexity: O(m * n) - we may need space to keep track of guarded cells if implemented naively.

Solution

To solve this problem, we can use the following approach:

  1. Create a grid to represent the state of each cell (guarded or unguarded) based on the positions of guards and walls.
  2. Mark the positions of guards and walls in the grid.
  3. For each guard, propagate its sight in all four directions until a wall or another guard blocks the view.
  4. Finally, count all cells that are unguarded and not occupied by guards or walls.

This approach ensures that we cover all possible cells that can be guarded by the guards in the grid.

Code Solutions

def countUnguarded(m, n, guards, walls):
    grid = [[0] * n for _ in range(m)]
    
    # Mark guards and walls in the grid
    for r, c in guards:
        grid[r][c] = 1  # 1 for guard
    for r, c in walls:
        grid[r][c] = 2  # 2 for wall

    # Directions for north, east, south, west
    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    
    # Mark guarded cells
    for r, c in guards:
        for dr, dc in directions:
            nr, nc = r, c
            while 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 0:
                grid[nr][nc] = 3  # Mark as guarded
                nr += dr
                nc += dc

    # Count unguarded cells
    unguarded_count = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 0:
                unguarded_count += 1

    return unguarded_count
← Back to All Questions