网格游戏

2017 年。网格游戏

难度：中等

主题：数组、矩阵、前缀和

给定一个 0 索引 大小为 2 x n 的二维数组网格，其中 grid[r][c] 表示矩阵上位置 (r, c) 处的点数。两个机器人正在这个矩阵上玩游戏。

两个机器人最初都从 (0, 0) 开始，并希望到达 (1, n-1)。每个机器人只能向右移动（(r, c) 到 (r, c 1)）或向下（(r, c) 到 (r 1, c)）。

游戏开始时，第一个机器人从 (0, 0) 移动到 (1, n-1)，收集其路径上单元格的所有点。对于路径上遍历的所有单元格 (r, c)，grid[r][c] 设置为 0。然后，第二个 机器人从 (0, 0) 移动到 (1, n-1) ），收集其路径上的点。请注意，它们的路径可能会相互交叉。

第一个机器人想要最小化第二个机器人收集的点数。相比之下，第二个机器人想要最大化它收集的点数。如果两个机器人都表现最佳，则返回第二个机器人收集的分数。

示例1：

• 输入： grid = [[2,5,4],[1,5,1]]
• 输出： 4
• 说明：第一个机器人所采取的最佳路径以红色显示，第二个机器人所采取的最佳路径以蓝色显示。
  第一个机器人访问的单元格设置为 0。
  第二个机器人将收集 0 0 4 0 = 4 分。

示例2：

• 输入： grid = [[3,3,1],[8,5,2]]
• 输出： 4
• 说明：第一个机器人所采取的最佳路径以红色显示，第二个机器人所采取的最佳路径以蓝色显示。
  第一个机器人访问的单元格设置为 0。
  第二个机器人将收集 0 3 1 0 = 4 分。

示例 3：

• 输入： grid = [[1,3,1,15],[1,3,3,1]]
• 输出： 7
• 说明：第一个机器人所采取的最佳路径以红色显示，第二个机器人所采取的最佳路径以蓝色显示。
  • 第一个机器人访问的单元格设置为 0。
  • 第二个机器人将收集 0 1 3 3 0 = 7 分。

约束：

• grid.length == 2
• n == grid[r].length
• 1 4
• 1 5

提示：

1. 第一个机器人移动到第二排时有n种选择。
2. 我们可以使用前缀和来帮助解决这个问题吗？

解决方案：

我们将使用以下方法：

1. 前缀和计算：我们将计算网格两行的前缀和，以有效计算任何子数组的点总和。

2. 模拟最佳运动:

   • 第一个机器人确定其路径，以最小化留给第二个机器人的点。
   • 在每个列转换时，第一个机器人可以选择向下移动，将网格分成两部分：
     • 上部剩余点：过渡列之后顶行的点。
     • 较低剩余点：过渡列之前的底行中的点。

3. 最小化第二个机器人的最大分数:

   • 在每次转换时，计算第二个机器人在第一个机器人的路径之后可以收集的最大点数。
   • 跟踪所有转换中这些最大值的最小值。

让我们用 PHP 实现这个解决方案：2017。网格游戏

<?php function gridGame($grid) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage
$grid1 = [[2, 5, 4], [1, 5, 1]];
$grid2 = [[3, 3, 1], [8, 5, 2]];
$grid3 = [[1, 3, 1, 15], [1, 3, 3, 1]];

echo gridGame($grid1) . "\n"; // Output: 4
echo gridGame($grid2) . "\n"; // Output: 4
echo gridGame($grid3) . "\n"; // Output: 7
?>

解释：

1. 前缀和计算:

   • prefixTop 和 prefixBottom 分别存储顶行和底行的累积和。
   • 这些可以实现高效的范围总和计算。

2. 模拟第一个机器人的路径：

   • 在每一列 i，第一个机器人可以决定在 i 列之后向下移动。
   • 这将网格分为两个区域：
     • 第 i 列之后的顶行（收集点：prefixTop[n] - prefixTop[i 1]）。
     • 第 i 列之前的底行（收集点：prefixBottom[i]）。

3. 第二个机器人的最优点:

   • 第二个机器人将占据剩余两个区域中的最大值。
   • 我们跟踪所有可能的转换的最大值中的最小值。

4. 复杂性：

   • 时间复杂度：O(n)，因为我们计算前缀和并循环遍历网格一次。
   • 空间复杂度：O(n)，由于前缀和数组。

示例演练

输入：网格 = [[2, 5, 4], [1, 5, 1]]

• 前缀和：
  • 前缀顶部 = [0, 2, 7, 11]
  • prefixBottom = [0, 1, 6, 7]
• 过渡点：
  • i = 0：顶部剩余 = 11 - 7 = 9，底部剩余 = 0 → 第二个机器人 = 9.
  • i = 1：顶部剩余 = 11 - 11 = 4，底部剩余 = 1 → 第二个机器人 = 4.
  • i = 2：顶部剩余 = 0，底部剩余 = 6 →第二个机器人= 6.
• 第二个机器人的最低分数: min(9, 4, 6) = 4.

这与预期输出相符。

联系链接

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

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

• 领英
• GitHub

以上是网格游戏的详细内容。更多信息请关注PHP中文网其他相关文章！