What is the key pattern in the Walking Robot Simulation problem?

The problem mainly relies on array scanning combined with hash table lookups to track robot movement and detect obstacles.

How do I efficiently simulate robot movement in this problem?

You simulate movement by updating the robot’s position according to commands while checking for obstacles using a hash table for efficient lookups.

Why do we return the squared Euclidean distance in this problem?

The squared Euclidean distance is requested to avoid the unnecessary computational cost of taking square roots, as it provides the same relative comparison.

What should I do if the robot runs into an obstacle?

If the robot encounters an obstacle, it should stop moving in that direction and proceed with the next command.

How do I handle multiple obstacles in the grid?

Store all obstacle positions in a hash table, allowing for efficient constant-time checks to see if the robot’s next position is blocked.

#874

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

模拟行走机器人

机器人在一个无限大小的 XY 网格平面上行走，从点 (0, 0) 处开始出发，面向北方。该机器人可以接收以下三种类型的命令 commands ： -2 ：向左转 90 度 -1 ：向右转 90 度 1 ：向前移动 x 个单位长度在网格上有一些格子被视为障碍物 obstacles 。第 i 个障碍物…

数组哈希表模拟

题目描述

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

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

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

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

返回机器人距离原点的 最大欧式距离 的平方。（即，如果距离为 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² + 4² = 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² + 8² = 65

示例 3：

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

提示：

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

lightbulb

解题思路

方法一：哈希表 + 模拟

我们定义一个长度为 $5$ 的方向数组 $dirs=[0, 1, 0, -1, 0]$ ，数组中的相邻两个元素表示一个方向。即 $(dirs[0], dirs[1])$ 表示向北，而 $(dirs[1], dirs[2])$ 表示向东，以此类推。

我们使用一个哈希表 $s$ 来存储所有障碍物的坐标，这样可以在 $O(1)$ 的时间内判断下一步是否会遇到障碍物。

另外，使用两个变量 $x$ 和 $y$ 来表示机器人当前所在的坐标，初始时 $x = y = 0$ 。变量 $k$ 表示机器人当前的方向，答案变量 $ans$ 表示机器人距离原点的最大欧式距离的平方。

接下来，我们遍历数组 $commands$ 中的每个元素 $c$ ：

如果 $c = -2$ ，表示机器人向左转 $90$ 度，即 $k = (k + 3) \bmod 4$ ；
如果 $c = -1$ ，表示机器人向右转 $90$ 度，即 $k = (k + 1) \bmod 4$ ；
否则，表示机器人向前移动 $c$ 个单位长度。我们将机器人当前的方向 $k$ 与方向数组 $dirs$ 结合，即可得到机器人在 $x$ 轴和 $y$ 轴上的增量。我们将 $c$ 个单位长度的增量分别累加到 $x$ 和 $y$ 上，并判断每次移动后的新坐标 $(nx, ny)$ 是否在障碍物的坐标中，如果不在，则更新答案 $ans$ ，否则停止模拟，进行下一条指令的模拟。

最后返回答案 $ans$ 即可。

时间复杂度 $O(C \times n + m)$ ，空间复杂度 $O(m)$ 。其中 $C$ 表示每次可以移动的最大步数，而 $n$ 和 $m$ 分别表示数组 $commands$ 和数组 $obstacles$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
        dirs = (0, 1, 0, -1, 0)
        s = {(x, y) for x, y in obstacles}
        ans = k = 0
        x = y = 0
        for c in commands:
            if c == -2:
                k = (k + 3) % 4
            elif c == -1:
                k = (k + 1) % 4
            else:
                for _ in range(c):
                    nx, ny = x + dirs[k], y + dirs[k + 1]
                    if (nx, ny) in s:
                        break
                    x, y = nx, ny
                    ans = max(ans, x * x + y * y)
        return ans

speed

复杂度分析

指标	值
时间	O(m + n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Test the candidate's ability to break down movement into discrete steps and efficiently track position.
question_mark
Look for knowledge of hash tables and how they can optimize obstacle detection.
question_mark
Assess the candidate’s understanding of Euclidean distance and its application to this problem.

warning

常见陷阱

外企场景

error
Failing to correctly handle turning directions or obstacles can cause incorrect movement simulation.
error
Not using a hash table for obstacles may lead to inefficient checks and higher time complexity.
error
Misunderstanding the problem’s requirement to return the squared Euclidean distance rather than the distance itself.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider different grid sizes or obstacles positioned in challenging ways.
arrow_right_alt
Experiment with larger command sequences and test the performance of your solution.
arrow_right_alt
Allow the robot to face multiple directions with different step sizes to introduce additional complexity.

help

常见问题

外企场景

继续练习

#1275 找出井字棋的获胜者 #1562 查找大小为 M 的最新分组 #873 最长的斐波那契子序列的长度