Problem Statement in English

You’re given a grid of size m x n, with some cells containing guards and some containing walls.

A guard can see all the cells in its row and column until its view is blocked by a wall or another guard. Your task is to count the number of unguarded cells in the grid.

Approach

This is an implementation problem where we simulate the vision of each guard in all four directions (up, down, left, right) until we hit a wall or another guard. We can use a 2D list to represent the grid and mark the cells that are guarded.

Solution in Python

  • This code was an improved version of mine, made by AI. It is well optimized and clean.

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

        for gx, gy in guards:
            matrix[gx][gy] = 2
        for wx, wy in walls:
            matrix[wx][wy] = 3
            wall_set.add((wx, wy))

        for gx, gy in guards:
            for dx, dy in directions:
                nx, ny = gx + dx, gy + dy
                while 0 <= nx < m and 0 <= ny < n and (matrix[nx][ny] != 3 and matrix[nx][ny] != 2):
                    matrix[nx][ny] = 1
                    nx += dx
                    ny += dy

        return sum(matrix[i][j] == 0 for i in range(m) for j in range(n))

Complexity

  • Time: O(m×n)O(m \times n)
    Since we iterate through each cell in the grid a constant number of times.

  • Space: O(m×n)O(m \times n)
    Since we are using a 2D list to represent the grid.

And we are done.