M874.模拟行走机器人

implementation, https://leetcode.cn/problems/walking-robot-simulation/

机器人在一个无限大小的 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) ，距离为 3^2 + 4^2 = 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) ，距离为 1^2 + 8^2 = 65

示例 3：

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

提示：

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

这是一个典型的模拟问题。我们需要维护机器人的当前位置 (x, y) 和当前的方向，然后按照指令一步步移动。

核心解题思路：

方向控制：我们可以定义一个方向数组 dx = [0, 1, 0, -1] 和 dy = [1, 0, -1, 0]。
- 索引 0, 1, 2, 3 分别代表 北、东、南、西。
- 右转 (-1)：索引 (di + 1) % 4。
- 左转 (-2)：索引 (di + 3) % 4（或者说 (di - 1) % 4，加 3 是为了防止负数）。
障碍物查找：为了快速判断当前坐标是否是障碍物，我们将障碍物列表转换为一个 哈希集合 (Set)。查找的时间复杂度从 $O (N)$ 降到 $O (1)$ 。
模拟移动：对于移动命令 x，我们需要一步一步走。每走一步，先计算下一步的坐标。如果是障碍物，则停止当前指令，保持在原位。
记录最大距离：每执行完一步移动（包括小步），计算一次当前的距离平方 $x^{2} + y^{2}$ ，并更新最大值。

代码实现：

python

class Solution:
    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
        # 定义四个方向：北(0,1), 东(1,0), 南(0,-1), 西(-1,0)
        dx = [0, 1, 0, -1]
        dy = [1, 0, -1, 0]
        
        # 初始位置在 (0, 0)，初始方向朝北 (索引为0)
        x, y, di = 0, 0, 0
        
        # 将障碍物转化为集合，提高查找效率 (x, y) 元组作为键
        obstacle_set = {tuple(o) for o in obstacles}
        
        max_dist_sq = 0
        
        for cmd in commands:
            if cmd == -2:  # 左转 90 度
                di = (di + 3) % 4
            elif cmd == -1:  # 右转 90 度
                di = (di + 1) % 4
            else:
                # 移动 cmd 个单位
                for _ in range(cmd):
                    next_x = x + dx[di]
                    next_y = y + dy[di]
                    
                    # 检查下一步是否是障碍物
                    if (next_x, next_y) not in obstacle_set:
                        x, y = next_x, next_y
                        # 每次移动后更新最大距离平方
                        max_dist_sq = max(max_dist_sq, x*x + y*y)
                    else:
                        # 遇到障碍物，停止当前指令
                        break
                        
        return max_dist_sq

复杂度分析：

时间复杂度： $O (N + M + K)$ 。
- $M$ 是障碍物的数量，用于初始化哈希集合。
- $N$ 是命令的数量。
- $K$ 是所有移动命令的总步数（由于 $1 \leq x \leq 9$ ，步数最多为 $9 N$ ）。
空间复杂度： $O (M)$ 。
- 我们需要一个集合来存储所有的障碍物坐标。
注意事项：
题目要求的是最大距离平方，所以每次移动一步后都需要进行 max 比较。
Python 中使用 tuple(o) 作为集合的元素，因为列表是不可哈希的（unhashable）。

M874.模拟行走机器人 ​

M874.模拟行走机器人