2257. 统计网格图中没有被保卫的格子数

给你两个整数 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：被看到（保卫）

• 从每个警卫出发，向四个方向一直走，直到：

  1. 出界
  2. 遇到墙 ('W')
  3. 遇到另一个警卫 ('G')（因为警卫会挡住视线，所以不能透过警卫看更远）

• 注意：警卫本身所在位置也是被保卫的（因为自己能看到自己所在格子，并且警卫位置初始时已经标记为 'G'，我们可以在标记看到时跳过 'G' 和 'W' 的阻挡判断，但注意不能重复标记为 1 如果已经是 'G' 或 'W' 的话，不过不影响计数，因为最后统计的是空格子未被看到的数量）。

---

3. 算法步骤

1. 创建一个 m × n 的数组 grid，初始化为 0（表示空格子，未被看到）。
2. 把所有的墙位置标记为 'W'。
3. 把所有的警卫位置标记为 'G'。
4. 对每个警卫 (r, c)：
   • 向上、下、左、右四个方向直线扫描：
     • 从该方向的下一个格子开始（因为警卫自身已经是 'G'，不需要再标记为看到）
     • 沿着方向一直走，如果遇到 'W' 或 'G' 就停止这个方向。
     • 否则，将格子标记为 1（被看到），继续前进。
5. 最后遍历整个网格：
   • 如果 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;
};

代码说明

1. 初始化网格：创建一个 m × n 的二维数组，初始值为 0，表示空格子未被看到。

2. 标记墙和警卫：

   • 墙的位置标记为 'W'
   • 警卫的位置标记为 'G'

3. 视线传播：

   • 对于每个警卫，向四个方向（上、右、下、左）直线扫描
   • 遇到边界、墙或另一个警卫时停止
   • 其他空格子标记为 1 表示被看到

4. 统计结果：

   • 遍历整个网格，统计值仍为 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 是警卫的数量，在题目约束下是高效的。