给你两个整数 m 和 n 表示一个下标从 0 开始的 m x n 网格图。同时给你两个二维整数数组 guards 和 walls ，其中 guards[i] = [rowi, coli] 且 walls[j] = [rowj, colj] ，分别表示第 i 个警卫和第 j 座墙所在的位置。
一个警卫能看到 4 个坐标轴方向（即东、南、西、北）的 所有 格子，除非他们被一座墙或者另外一个警卫 挡住 了视线。如果一个格子能被 至少 一个警卫看到，那么我们说这个格子被 保卫 了。
请你返回空格子中，有多少个格子是 没被保卫 的。
好的，我们先一步步分析这个问题。
1. 问题理解
我们有一个 m × n 的网格，上面有：
- 警卫 (guards)：可以向四个方向（上、下、左、右）直线看到所有格子，直到被墙或另一个警卫挡住。
- 墙 (walls)：会阻挡视线。
- 如果一个格子能被至少一个警卫看到，它就是被保卫的。
- 问：有多少个格子是没被保卫的。
2. 思路
我们可以模拟每个警卫的视线传播过程。
-
用
grid[r][c]表示每个格子的状态：'G'：警卫'W'：墙0：初始状态（空格子，未被看到）1：被看到（保卫）
-
从每个警卫出发，向四个方向一直走，直到：
- 出界
- 遇到墙 (
'W') - 遇到另一个警卫 (
'G')（因为警卫会挡住视线，所以不能透过警卫看更远）
-
注意：警卫本身所在位置也是被保卫的（因为自己能看到自己所在格子，并且警卫位置初始时已经标记为
'G'，我们可以在标记看到时跳过'G'和'W'的阻挡判断，但注意不能重复标记为1如果已经是'G'或'W'的话，不过不影响计数，因为最后统计的是空格子未被看到的数量）。
3. 算法步骤
- 创建一个
m × n的数组grid，初始化为0（表示空格子，未被看到）。 - 把所有的墙位置标记为
'W'。 - 把所有的警卫位置标记为
'G'。 - 对每个警卫
(r, c)：- 向上、下、左、右四个方向直线扫描：
- 从该方向的下一个格子开始（因为警卫自身已经是
'G'，不需要再标记为看到） - 沿着方向一直走，如果遇到
'W'或'G'就停止这个方向。 - 否则，将格子标记为
1（被看到），继续前进。
- 从该方向的下一个格子开始（因为警卫自身已经是
- 向上、下、左、右四个方向直线扫描：
- 最后遍历整个网格：
- 如果
grid[i][j] == 0，说明是未被保卫的空格子，计数加一。
- 如果
4. 复杂度
- 每个警卫最多会扫描
O(m + n)个格子（四个方向加起来）。 - 总复杂度：
O(k * (m + n))，其中k是警卫数量。 - 在题目范围内可行。
以下是使用 JavaScript 实现的代码：
/*** @param {number} m* @param {number} n* @param {number[][]} guards* @param {number[][]} walls* @return {number}*/
var countUnguarded = function(m, n, guards, walls) {// 创建网格，0 表示空格子未被看到const grid = Array.from({ length: m }, () => Array(n).fill(0));// 标记墙的位置for (const [r, c] of walls) {grid[r][c] = 'W';}// 标记警卫的位置for (const [r, c] of guards) {grid[r][c] = 'G';}// 四个方向：上、右、下、左const dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]];// 每个警卫向四个方向看for (const [r, c] of guards) {for (const [dr, dc] of dirs) {let nr = r + dr;let nc = c + dc;// 沿这个方向一直走直到边界或阻挡while (nr >= 0 && nr < m && nc >= 0 && nc < n) {if (grid[nr][nc] === 'G' || grid[nr][nc] === 'W') {break; // 被阻挡}// 标记为被看到grid[nr][nc] = 1; // 1 表示被看到nr += dr;nc += dc;}}}// 统计未被看到的空格子let count = 0;for (let i = 0; i < m; i++) {for (let j = 0; j < n; j++) {if (grid[i][j] === 0) {count++;}}}return count;
};
代码说明
-
初始化网格：创建一个
m × n的二维数组，初始值为0，表示空格子未被看到。 -
标记墙和警卫：
- 墙的位置标记为
'W' - 警卫的位置标记为
'G'
- 墙的位置标记为
-
视线传播：
- 对于每个警卫，向四个方向（上、右、下、左）直线扫描
- 遇到边界、墙或另一个警卫时停止
- 其他空格子标记为
1表示被看到
-
统计结果：
- 遍历整个网格，统计值仍为
0的格子数量
- 遍历整个网格，统计值仍为
测试示例
// 测试代码
console.log(countUnguarded(4, 6,[[0,0],[1,1],[2,3]],[[0,1],[1,0],[1,2],[2,2],[2,1],[3,1],[3,3]]
)); // 输出结果
这个实现的时间复杂度是 O(k × (m + n))，其中 k 是警卫的数量，在题目约束下是高效的。