。行走机器人模拟

874。行走机器人模拟

难度：中等

主题：数组、哈希表、模拟

无限 XY 平面上的机器人从点 (0, 0) 开始，面向北。机器人可以接收这三种可能类型的命令的序列：

• -2：左转90度。
• -1：右转90度。
• 1

一些网格方块是障碍物。第 i 个障碍物位于网格点障碍物[i] = (x_i, y_i)。如果机器人遇到障碍物，那么它会留在当前位置并继续执行下一个命令。

返回机器人从原点得到的最大欧氏距离平方（即如果距离为5，则返回25）。

注意：

• 北意味着+Y方向。
• 东意味着+X方向。
• 南意味着-Y方向。
• 西意味着-X方向。
• [0,0] 内可能存在障碍物。

示例1：

• 输入： 命令 = [4,-1,3]，障碍 = []
• 输出： 25
• 说明：机器人从 (0, 0) 开始：
  1. 向北移动 4 个单位到 (0, 4)。
  2. 右转。
  3. 向东移动 3 个单位到 (3, 4)。
  4. 机器人距离原点最远的点是 (3, 4)，其平方为 32 + 42 = 25 个单位。

示例2：

• 输入： 命令 = [4,-1,4,-2,4]，障碍 = [[2,4]]
• 输出： 65
• 说明：机器人从 (0, 0) 开始：
  1. 向北移动 4 个单位到 (0, 4)。
  2. 右转。
  3. 向东移动1个单位，被(2, 4)处的障碍物阻挡，机器人位于(1, 4)处。
  4. 左转。
  5. 向北移动 4 个单位到 (1, 8)。
  6. 机器人距离原点最远的点是 (1, 8)，其平方为 12 + 82 = 65 个单位。

示例 3：

• 输入： 命令 = [6,-1,-1,6]，障碍 = []
• 输出： 36
• 解释：机器人从 (0, 0) 开始：
  1. 向北移动 6 个单位到 (0, 6)。
  2. 右转。
  3. 右转。
  4. 向南移动 6 个单位到 (0, 0)。
  5. 机器人距离原点最远的点是 (0, 6)，其平方为 62 = 36 个单位。

约束：

• 1 4
• 命令[i] 是 -2、-1 或 [1, 9] 范围内的整数。
• 0 4
• -3 * 10⁴ i, y_i 4
• 答案保证小于2³¹

解决方案：

我们需要根据一系列命令在无限二维网格上模拟机器人的运动，并避开障碍物（如果有）。目标是确定机器人从原点到达的最大欧氏距离平方。

方法

1. 方向处理:

   • 机器人可以面向四个方向之一：北、东、南、西。
   • 我们可以将这些方向表示为向量：
     • 北：(0, 1)
     • 东：(1, 0)
     • 南：(0, -1)
     • 西：(-1, 0)

2. 转向：

   • 左转（-2）会将方向逆时针旋转 90 度。
   • 右转 (-1) 会将方向顺时针旋转 90 度。

3. 运动：

   • 对于每个移动命令，机器人都会朝当前方向移动，一次移动一个单位。如果遇到障碍物，它会根据该命令停止移动。

4. 追踪障碍：

   • 将障碍物列表转换为一组元组以便快速查找，让机器人快速判断是否会碰到障碍物。

5. 距离计算:

   • 跟踪机器人在运动过程中到达的距原点平方的最大距离。

让我们用 PHP 实现这个解决方案：874。行走机器人模拟

<?php
/**
 * @param Integer[] $commands
 * @param Integer[][] $obstacles
 * @return Integer
 */
function robotSim($commands, $obstacles) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo robotSim([4,-1,3], []) . "\n"; // Output: 25
echo robotSim([4,-1,4,-2,4], [[2,4]]) . "\n"; // Output: 65
echo robotSim([6,-1,-1,6], []) . "\n"; // Output: 36
?>

解释：

• 方向管理：我们使用向量列表来表示方向，可以轻松计算移动后的下一个位置。
• 障碍物检测：通过将障碍物存储在集合中，我们实现了 O(1) 时间复杂度来检查某个位置是否被障碍物阻挡。
• 距离计算：我们不断更新机器人移动时到达的最大平方距离。

测试用例

• 提供的示例测试用例用于验证解决方案：
  • [4,-1,3] 没有障碍物应返回 25。
  • [4,-1,4,-2,4] 有障碍物 [[2,4]] 应返回 65。
  • [6,-1,-1,6] 没有障碍物应返回 36。

该解决方案有效地处理了问题约束并根据需要计算最大距离平方。

联系链接

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

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

• 领英
• GitHub

以上是。行走机器人模拟的详细内容。更多信息请关注PHP中文网其他相关文章！