计算网格中不受保护的单元格

2257。计算网格中不受保护的单元

难度：中等

主题：数组、矩阵、模拟

给定两个整数 m 和 n，表示 0 索引 m x n 网格。您还获得两个 2D 整数数组 Guards 和 Walls，其中 Guards[i] = [row_i, col_i] 和 Walls[j] = [row_j, col_j] 代表第 i^th 个守卫的位置，分别是第 j 面墙。

警卫可以从其位置开始看到四个基本方向（北、东、南或西）的每个牢房，除非被墙壁或其他警卫阻挡。如果有至少一名守卫可以看到某个牢房，则该牢房受到看守。

返回不受保护的未占用单元格的数量。

示例1：

• 输入： m = 4, n = 6, 守卫 = [[0,0],[1,1],[2,3]], 墙壁 = [[0,1],[2, 2],[1,4]]
• 输出： 7
• 说明：上图中，受保护和不受保护的单元格分别以红色和绿色显示。
  • 总共有 7 个无人看守的单元格，所以我们返回 7 个。

示例2：

• 输入： m = 3, n = 3, 守卫 = [[1,1]], 墙壁 = [[0,1],[1,0],[2,1],[1, 2]]
• 输出： 4
• 说明：未受保护的单元格在上图中以绿色显示。
  • 总共有 4 个无人看守的单元格，所以我们返回 4 个。

约束：

• 1 5
• 2 5
• 1 4
• 2
• 守卫[i].length == 墙[j].length == 2
• 0 i，行_j
• 0 i, col_j
• 守卫和墙壁中的所有位置都是独特。

提示：

1. 创建一个二维数组来表示网格。你能标记出守卫可以看到的方块吗？
2. 迭代守卫，并针对 4 个方向中的每一个，推进当前图块并标记该图块。什么时候应该停止前进？

解决方案：

我们需要标记至少由一名守卫看守的单元格。守卫可以看到四个基本方向（北、南、东、西），但他们的视线被墙壁阻挡。我们可以模拟这个过程并计算不受保护的单元格的数量。

方法：

1. 创建一个网格：我们可以将网格表示为一个二维数组，其中每个单元格可以是墙、守卫或空。
2. 标记被看守的单元格：对于每个守卫，在四个方向（北、南、东、西）迭代并标记它能看到的所有单元格，当遇到墙壁或另一个守卫时停止。
3. 计算不受看守的单元格：标记受看守的单元格后，计算有多少个单元格不受看守且不是墙。

步骤：

1. 网格初始化：创建一个二维数组来表示网格。当我们迭代时，用墙壁、守卫和守卫区域标记单元格。

2. 模拟警卫覆盖范围:

   • 守卫可以看到四个方向（北、南、东、西）。
   • 标记每个守卫所看守的牢房，直到遇到墙壁或另一个守卫。

3. 计算不受看守的单元格：处理完所有守卫后，对既不是墙壁、守卫、也没有看守的单元格进行计数。

让我们用 PHP 实现这个解决方案：2257。计算网格中不受保护的单元格

<?php
/**
 * @param Integer $m
 * @param Integer $n
 * @param Integer[][] $guards
 * @param Integer[][] $walls
 * @return Integer
 */
function countUnguarded($m, $n, $guards, $walls) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
$m = 4;
$n = 6;
$guards = [[0, 0], [1, 1], [2, 3]];
$walls = [[0, 1], [2, 2], [1, 4]];
echo countUnguarded($m, $n, $guards, $walls); // Output: 7

// Example 2
$m = 3;
$n = 3;
$guards = [[1, 1]];
$walls = [[0, 1], [1, 0], [2, 1], [1, 2]];
echo countUnguarded($m, $n, $guards, $walls); // Output: 4
?>

解释：

1. 初始化:

   • 对于空单元格，网格初始化为 0。墙壁和守卫都标有独特的常量。

2. 守卫模拟：

   • 对于每个守卫，模拟所有四个方向的移动，将单元标记为受守卫，直到撞到墙壁或另一个守卫。

3. 计算不受保护的细胞:

   • 处理完所有守卫后，迭代网格并计算仍标记为 0 的单元格。

表现：

• 时间复杂度：O(m x n g x d)，其中 g 是守卫的数量，d 是每个守卫可以移动的方向上的单元格数量旅行。
• 空间复杂度：O(m x n) 对于网格。

时间复杂度：

• 网格初始化：_O(m * n)，其中_m和n 是网格的尺寸。
• 标记警卫视野：每个警卫最多检查行或列在四个方向上的长度。所以，对于每个守卫，它是O(m n)。
• 计算不受保护的细胞：O(m * n).

因此，整体复杂度为 O(m * n)，在给定问题约束的情况下，这是有效的。

边缘情况：

• 如果没有守卫或墙壁存在，整个网格将无人守卫。
• 如果所有单元格都有防护或有墙，则结果将为 0 个未防护单元格。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是计算网格中不受保护的单元格的详细内容。更多信息请关注PHP中文网其他相关文章！