模拟行走机器人
字数 3487 2025-12-23 04:12:48
模拟行走机器人
题目描述
你在一个无限大的网格上，从 (0, 0) 点开始，面朝北方。机器人可以接收三种指令：
-2：向左转 90 度。-1：向右转 90 度。1 <= x <= 9：沿当前方向前进x个单位长度。
此外，网格上还有一些障碍物。机器人在前进过程中，如果下一个移动的目标格子存在障碍物，它将停在障碍物前一个格子（即不会踏上障碍物），并继续执行下一条指令。
给定一个包含障碍物坐标的数组 obstacles 和一个指令数组 commands，请你计算机器人执行完所有指令后，距离原点的最大欧式距离（即 sqrt(x^2 + y^2)）。注意只需要计算整个过程中的最大距离，而不是最终距离。
示例：
输入：commands = [4, -1, 4, -2, 4], obstacles = [[2, 4]]
输出：65
解释：机器人的路径如下：
- 前进4个单位到 (0, 4)。
- 向右转，面朝东方。
- 前进4个单位，但遇到障碍物 (2, 4)（因为目标格子 (4, 4) 需要经过 (1,4)，(2,4)，(3,4)，(4,4)，其中(2,4)是障碍），所以停在障碍物前一个格子，即 (1, 4)。
- 向左转，面朝北方。
- 前进4个单位到 (1, 8)。
整个过程距离原点的最远距离是1^2 + 8^2 = 65。
解题过程
步骤一：问题理解与核心难点
这个题目的核心是模拟机器人的行走过程，并在模拟中处理障碍物。难点在于：
- 方向变化：如何高效地表示和处理“左转”、“右转”带来的方向变化。
- 障碍物检测：机器人是一步一步移动的，但指令
x可能意味着连续移动多步。在每一步移动前，都必须检查前方目标格子是否是障碍物。如果使用朴素方法，每次都在obstacles列表中线性查找，时间复杂度会很高。 - 距离计算：只需要记录过程中的最大欧式距离的平方即可（因为比较大小不需要开方）。
步骤二：数据结构选择
为了高效检测障碍物，我们需要将障碍物的坐标存储在一个能快速查询的数据结构中。由于网格坐标是整数对 (x, y)，我们可以使用哈希集合（HashSet 或 Set）来存储。
- 我们将每个障碍物的坐标
(x, y)转换为一个唯一的字符串（如“x,y”）或一个长整型（如((long)x << 32) | ((long)y & 0xffffffffL)）作为键存入集合。 - 这样，判断一个坐标是否是障碍物，其时间复杂度可以降至平均 O(1)。
为什么选择哈希集合？
因为我们需要频繁执行 contains 操作来检查某个坐标是否是障碍物。哈希表的平均 O(1) 查找时间远优于数组的线性查找 O(n) 或排序后二分查找 O(log n)。
步骤三：方向表示与移动向量
机器人有四个方向：北(N)，东(E)，南(S)，西(W)。我们可以用一个数组来表示这四个方向。
- 定义方向数组：
dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]][0, 1]：向北移动（x不变，y增加）[1, 0]：向东移动（x增加，y不变）[0, -1]：向南移动（x不变，y减少）[-1, 0]：向西移动（x减少，y不变）
- 我们用一个索引
dirIndex（初始为0）来记录当前方向。它对应dirs数组的索引。dirIndex = 0：面朝北方。- 右转（
-1）：dirIndex = (dirIndex + 1) % 4。例如，从北(0)转到东(1)。 - 左转（
-2）：dirIndex = (dirIndex - 1 + 4) % 4。例如，从北(0)转到西(3)。
这样，方向变换就变成了简单的索引运算。
步骤四：模拟流程算法步骤
-
初始化：
- 当前位置
x = 0,y = 0。 - 当前方向索引
dirIndex = 0（向北）。 - 最大距离平方
maxDistSq = 0。 - 将障碍物列表
obstacles中的所有坐标转换为字符串（或长整型）并存入一个哈希集合obstacleSet。
- 当前位置
-
处理每条指令：
- 如果指令是
-1：dirIndex = (dirIndex + 1) % 4。 - 如果指令是
-2：dirIndex = (dirIndex - 1 + 4) % 4。 - 如果指令是正整数
steps：- 获取当前方向的移动向量：
[dx, dy] = dirs[dirIndex]。 - 循环
steps次：- 计算下一个目标位置：
nextX = x + dx,nextY = y + dy。 - 如果
(nextX, nextY)在obstacleSet中：- 说明是障碍物，停止本次移动，不更新
(x, y)，并跳出本次steps循环。
- 说明是障碍物，停止本次移动，不更新
- 否则（不是障碍物）：
- 更新当前位置：
x = nextX,y = nextY。 - 计算当前距离原点的平方：
currentDistSq = x*x + y*y。 - 更新最大距离：
maxDistSq = max(maxDistSq, currentDistSq)。
- 更新当前位置：
- 计算下一个目标位置：
- 获取当前方向的移动向量：
- 如果指令是
-
返回结果：
- 所有指令执行完毕后，返回
maxDistSq。
- 所有指令执行完毕后，返回
步骤五：举例详解（使用题目示例）
输入：commands = [4, -1, 4, -2, 4], obstacles = [[2, 4]]
- 初始化：
(x, y) = (0, 0),dirIndex = 0(北),maxDistSq = 0,obstacleSet = {“2,4”}。 - 指令
4(向北走4步)：- 方向向量
[0, 1]。 - 第1步：
next(0,1)不在障碍集，移动至(0,1)，maxDistSq = max(0, 1) = 1。 - 第2步：
next(0,2)不在障碍集，移动至(0,2)，maxDistSq = max(1, 4) = 4。 - 第3步：
next(0,3)不在障碍集，移动至(0,3)，maxDistSq = max(4, 9) = 9。 - 第4步：
next(0,4)不在障碍集，移动至(0,4)，maxDistSq = max(9, 16) = 16。
- 方向向量
- 指令
-1(右转)：dirIndex = (0 + 1) % 4 = 1(东)。 - 指令
4(向东走4步)：- 方向向量
[1, 0]。 - 第1步：
next(1,4)不在障碍集，移动至(1,4)，maxDistSq = max(16, 17) = 17。 - 第2步：
next(2,4)在障碍集！停止移动，当前位置保持在(1,4)。
- 方向向量
- 指令
-2(左转)：dirIndex = (1 - 1 + 4) % 4 = 0(北)。 - 指令
4(向北走4步)：- 方向向量
[0, 1]。 - 第1步：
next(1,5)不在障碍集，移动至(1,5)，maxDistSq = max(17, 26) = 26。 - 第2步：
next(1,6)不在障碍集，移动至(1,6)，maxDistSq = max(26, 37) = 37。 - 第3步：
next(1,7)不在障碍集，移动至(1,7)，maxDistSq = max(37, 50) = 50。 - 第4步：
next(1,8)不在障碍集，移动至(1,8)，maxDistSq = max(50, 65) = 65。
- 方向向量
- 返回
maxDistSq = 65。
步骤六：复杂度分析
- 时间复杂度：O(N + K)，其中 N 是
commands指令总数（注意每个移动指令会拆解成一步步执行，总步数不超过 9N），K 是障碍物数量。构建哈希集合 O(K)，模拟过程 O(N)。 - 空间复杂度：O(K)，用于存储障碍物的哈希集合。
关键点总结：
- 使用方向数组和索引是处理转向的简洁方法。
- 使用哈希集合存储障碍物坐标是实现高效检测的核心，它避免了在每一步移动时都遍历整个障碍物列表。
- 模拟时必须单步移动，并在每一步前检查障碍物，以确保在障碍物前停下。
- 结果只需返回过程中最大距离的平方，无需开方。