调试中...
调试中...
题目描述
题目描述
题解
题解
提交记录
提交记录
代码
代码
测试用例
测试用例
测试结果
测试结果
中等
相关标签
相关企业
提示

给你两个整数 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 <= 105
  • 2 <= m * n <= 105
  • 1 <= guards.length, walls.length <= 5 * 104
  • 2 <= guards.length + walls.length <= m * n
  • guards[i].length == walls[j].length == 2
  • 0 <= rowi, rowj < m
  • 0 <= coli, colj < n
  • guards 和 walls 中所有位置 互不相同 。
通过次数
6.4K
提交次数
12.1K
通过率
52.9%

相关标签

相关企业

提示 1
Create a 2D array to represent the grid. Can you mark the tiles that can be seen by a guard?

提示 2
Iterate over the guards, and for each of the 4 directions, advance the current tile and mark the tile. When should you stop advancing?


评论 (0)

贡献者
© 2025 领扣网络(上海)有限公司
0 人在线
行 1,列 1
运行和提交代码需要登录
m =
4
n =
6
guards =
[[0,0],[1,1],[2,3]]
walls =
[[0,1],[2,2],[1,4]]
Source