模拟行走机器人

标签: 数组 哈希表 模拟

难度: Medium

机器人在一个无限大小的 XY 网格平面上行走，从点 (0, 0) 处开始出发，面向北方。该机器人可以接收以下三种类型的命令 commands ：

  • -2 ：向左转 90 度
  • -1 ：向右转 90 度
  • 1 <= x <= 9 ：向前移动 x 个单位长度

在网格上有一些格子被视为障碍物 obstacles 。第 i 个障碍物位于网格点  obstacles[i] = (xi, yi) 。

机器人无法走到障碍物上，它将会停留在障碍物的前一个网格方块上，并继续执行下一个命令。

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

 

注意：

  • 北方表示 +Y 方向。
  • 东方表示 +X 方向。
  • 南方表示 -Y 方向。
  • 西方表示 -X 方向。
  • 原点 [0,0] 可能会有障碍物。

示例 1：

输入：commands = [4,-1,3], obstacles = []
输出：25
解释：
机器人开始位于 (0, 0)：
1. 向北移动 4 个单位，到达 (0, 4)
2. 右转
3. 向东移动 3 个单位，到达 (3, 4)
距离原点最远的是 (3, 4) ，距离为 32 + 42 = 25

示例 2：

输入：commands = [4,-1,4,-2,4], obstacles = [[2,4]]
输出：65
解释：机器人开始位于 (0, 0)：
1. 向北移动 4 个单位，到达 (0, 4)
2. 右转
3. 向东移动 1 个单位，然后被位于 (2, 4) 的障碍物阻挡，机器人停在 (1, 4)
4. 左转
5. 向北走 4 个单位，到达 (1, 8)
距离原点最远的是 (1, 8) ，距离为 12 + 82 = 65

示例 3：

输入：commands = [6,-1,-1,6], obstacles = []
输出：36
解释：机器人开始位于 (0, 0):
1. 向北移动 6 个单位，到达 (0, 6).
2. 右转
3. 右转
4. 向南移动 6 个单位，到达 (0, 0).
机器人距离原点最远的点是 (0, 6)，其距离的平方是 62 = 36 个单位。

提示：

  • 1 <= commands.length <= 104
  • commands[i] 的值可以取 -2、-1 或者是范围 [1, 9] 内的一个整数。
  • 0 <= obstacles.length <= 104
  • -3 * 104 <= xi, yi <= 3 * 104
  • 答案保证小于 231

Submission

运行时间: 68 ms

内存: 20.9 MB

class Solution:
    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
        dir4 = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        k = 0
        hs = set(map(tuple, obstacles))
        x, y = 0, 0
        ans = 0
        for cmd in commands:
            if cmd == -2:
                k = (k - 1) % 4
            elif cmd == -1:
                k = (k + 1) % 4
            else:
                dx, dy = dir4[k]
                for _ in range(cmd):
                    x2, y2 = x + dx, y + dy
                    if (x2, y2) in hs:
                        break
                    x, y = x2, y2
                ans = max(ans, x * x + y * y)  # 只需在终点处计算
        return ans

Explain

这个题解首先定义了一个方向数组 dir4，该数组代表了机器人可以朝向的四个方向：北(0,1)，东(1,0)，南(0,-1)，和西(-1,0)。初始时机器人面向北方。题解中还定义了变量 k 来表示机器人当前的方向。对于每个命令，如果命令是 -2 或 -1，这表示机器人需要转向。转向操作通过改变索引 k 来实现，利用模运算确保 k 始终在 0 到 3 的范围内。如果命令是一个正数，机器人则向前移动指定的步数。在移动过程中，题解检查是否碰到障碍物。如果当前方向的下一步位置不是障碍物，则更新机器人的位置；如果是障碍物，则停止移动。每次移动后，题解都会计算并更新机器人离原点的最大欧式距离的平方。

时间复杂度: O(m)

空间复杂度: O(o)

class Solution:
    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
        dir4 = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 北, 东, 南, 西 方向的向量
        k = 0  # 初始方向为北
        hs = set(map(tuple, obstacles))  # 将障碍物列表转换为集合，用于快速查找
        x, y = 0, 0  # 机器人的初始位置
        ans = 0  # 记录最大距离的平方
        for cmd in commands:
            if cmd == -2:  # 左转90度
                k = (k - 1) % 4
            elif cmd == -1:  # 右转90度
                k = (k + 1) % 4
            else:  # 向前移动 cmd 步
                dx, dy = dir4[k]  # 获取当前方向的向量
                for _ in range(cmd):
                    x2, y2 = x + dx, y + dy
                    if (x2, y2) in hs:  # 检查新位置是否有障碍物
                        break
                    x, y = x2, y2
                ans = max(ans, x * x + y * y)  # 更新最大距离的平方
        return ans

Explore

在题解中，障碍物是通过集合来管理的，初始位置为(0, 0)。如果原点(0, 0)在障碍物集合中，实际上在这种情况下，机器人初始位置仍然设定为原点，并不会受到影响，因为机器人在原点开始并没有移动命令。机器人的移动仅在接收到向前的命令时受到障碍物的影响，而在原点有障碍物不影响机器人的初始状态，但会阻止机器人向该障碍物方向的移动。

方向数组dir4定义了四个元素，分别对应北、东、南、西的方向。当机器人接收到-2命令时，执行左转90度，即方向索引减1；接收到-1命令时，执行右转90度，即方向索引加1。使用模运算（%4）确保索引值始终在0到3之间，即使索引值变为负数或超过3，模运算也能将其正确地映射回0到3的范围内。这样可以保证无论机器人如何转向，都能够根据数组索引准确地获取到相应的方向向量。

当机器人遇到障碍物时，题解中的策略仅是停止当前命令的执行，即机器人停在障碍物前的最后一个位置，而不是停止所有后续命令的执行。机器人在遇到障碍物后，会继续接收并执行后续的命令。这意味着如果后续命令指示机器人转向或向不同方向移动，它仍然可以执行这些命令。

题解中确实没有提及如何处理命令数组中的非法值。在实际应用中，应该在处理命令之前验证每个命令的合法性。可以通过检查每个命令是否为-2, -1, 或是一个正整数。如果发现非法命令，可以选择忽略这些命令、抛出异常、或是停止执行，具体处理方式取决于应用的需求和设计。