LeetCode 题解工作台
统计网格图中没有被保卫的格子数
给你两个整数 m 和 n 表示一个下标从 0 开始的 m x n 网格图。同时给你两个二维整数数组 guards 和 walls ，其中 guards[i] = [row i , col i ] 且 walls[j] = [row j , col j ] ，分别表示第 i 个警卫和第 j 座墙所在的…
3
题型
8
代码语言
3
相关题
当前训练重点
中等 · 数组·matrix
答案摘要
我们创建一个 $m \times n$ 的二维数组 ，其中 表示第 行第 列的格子。初始时 的值为 ，表示该格子没有被保卫。 然后遍历所有的警卫和墙，将 的值置为 ，这些位置不能被访问。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·matrix 题型思路
题目描述
给你两个整数 m 和 n 表示一个下标从 0 开始的 m x n 网格图。同时给你两个二维整数数组 guards 和 walls ，其中 guards[i] = [rowi, coli] 且 walls[j] = [rowj, colj] ，分别表示第 i 个警卫和第 j 座墙所在的位置。
一个警卫能看到 4 个坐标轴方向（即东、南、西、北）的 所有 格子，除非他们被一座墙或者另外一个警卫 挡住 了视线。如果一个格子能被 至少 一个警卫看到，那么我们说这个格子被 保卫 了。
请你返回空格子中，有多少个格子是 没被保卫 的。
示例 1：
输入：m = 4, n = 6, guards = [[0,0],[1,1],[2,3]], walls = [[0,1],[2,2],[1,4]] 输出：7 解释：上图中，被保卫和没有被保卫的格子分别用红色和绿色表示。 总共有 7 个没有被保卫的格子，所以我们返回 7 。
示例 2：
输入：m = 3, n = 3, guards = [[1,1]], walls = [[0,1],[1,0],[2,1],[1,2]] 输出：4 解释：上图中，没有被保卫的格子用绿色表示。 总共有 4 个没有被保卫的格子，所以我们返回 4 。
提示：
1 <= m, n <= 1052 <= m * n <= 1051 <= guards.length, walls.length <= 5 * 1042 <= guards.length + walls.length <= m * nguards[i].length == walls[j].length == 20 <= rowi, rowj < m0 <= coli, colj < nguards和walls中所有位置 互不相同 。
解题思路
方法一：模拟
我们创建一个 的二维数组 ，其中 表示第 行第 列的格子。初始时 的值为 ，表示该格子没有被保卫。
然后遍历所有的警卫和墙，将 的值置为 ，这些位置不能被访问。
接下来，我们遍历所有警卫的位置，从该位置出发，向四个方向进行模拟，直到遇到墙或警卫，或者越界。在模拟的过程中，将遇到的格子的值置为 ，表示该格子被保卫。
最后，我们遍历 ，统计值为 的格子的个数，即为答案。
时间复杂度 ，空间复杂度 。其中 和 分别为网格的行数和列数。
class Solution:
def countUnguarded(
self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]
) -> int:
g = [[0] * n for _ in range(m)]
for i, j in guards:
g[i][j] = 2
for i, j in walls:
g[i][j] = 2
dirs = (-1, 0, 1, 0, -1)
for i, j in guards:
for a, b in pairwise(dirs):
x, y = i, j
while 0 <= x + a < m and 0 <= y + b < n and g[x + a][y + b] < 2:
x, y = x + a, y + b
g[x][y] = 1
return sum(v == 0 for row in g for v in row)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(m \times n) |
| 空间 | O(m \times n) |
面试官常问的追问
外企场景- question_mark
The interviewer mentions creating a 2D grid and marking visible tiles, which points directly to matrix simulation.
- question_mark
They emphasize that guards stop at walls or other guards, which means blocker checks matter more than path length.
- question_mark
They ask for unoccupied and unguarded cells specifically, which suggests separating cell states before counting.
常见陷阱
外企场景- error
Marking through another guard or wall instead of stopping the scan immediately.
- error
Counting watched cells incorrectly because guard and wall cells were never given distinct states.
- error
Trying to use generic BFS or DFS even though this problem is about straight-line row and column visibility.
进阶变体
外企场景- arrow_right_alt
Return the list of unguarded coordinates instead of just the count.
- arrow_right_alt
Allow diagonal vision, which changes the simulation from four directions to eight.
- arrow_right_alt
Process online updates where guards or walls are added after the initial grid is built.