LeetCode 2069：机器人路径模拟与边界处理技巧

1. 题目背景与需求解析

今天要拆解的是LeetCode第2069题"模拟行走机器人二"，这是一道典型的机器人路径模拟类题目。这类题目在面试中经常出现，主要考察对二维空间移动和边界条件的处理能力。

题目要求我们模拟一个机器人在网格上的移动过程。机器人初始位于坐标(0,0)位置，面朝北方。网格的边界由width和height参数定义。我们需要实现一个Robot类，包含以下方法：

• Robot(int width, int height)：初始化网格尺寸
• void step(int num)：让机器人前进num步
• int[] getPos()：返回当前坐标
• String getDir()：返回当前朝向

关键点：机器人移动的特点是到达边界后会"绕回"，即从网格的另一侧重新出现。比如在5x5网格中，从(4,0)向东移动一步会到达(0,0)。

1.1 题目难点分析

这道题看似简单，但有几个容易踩坑的地方：

1. 移动步数优化：当num远大于网格周长时，直接一步步模拟会超时。比如100x100网格，num=1e9时，需要优化计算。

2. 方向处理：机器人有四个基本方向（北、东、南、西），每次转向90度。需要正确处理方向变化与坐标变化的对应关系。

3. 边界条件：特别注意当机器人正好位于角落时的转向行为。比如在(0,0)位置面朝北，再向北移动应该转向东。

4. 初始方向：题目明确机器人初始面朝北方，这个细节容易被忽略。

2. 解决方案设计与实现

2.1 数据结构选择

我们需要高效地跟踪机器人的状态，包括：

• 当前位置(x,y)
• 当前方向
• 网格尺寸

使用一个类来封装这些属性是最直观的选择：

class Robot: def __init__(self, width: int, height: int): self.width = width self.height = height self.x = 0 self.y = 0 self.direction = 0 # 0:North, 1:East, 2:South, 3:West

2.2 移动算法优化

直接模拟每一步移动在num很大时效率太低。优化思路是：

1. 计算网格周长：perimeter = 2*(width + height) - 4
2. 实际有效移动步数：num %= perimeter
3. 处理余下的步数

注意：当num正好是周长的整数倍时，机器人会回到原点，但方向可能改变。需要特殊处理这种情况。

实现代码：

def step(self, num: int) -> None: perimeter = 2 * (self.width + self.height) - 4 num %= perimeter if num == 0 and (self.x, self.y) == (0, 0): self.direction = 3 # 特殊处理回到原点情况 for _ in range(num): self._single_step()

2.3 单步移动实现

处理单步移动需要考虑当前方向和边界条件：

def _single_step(self): # 尝试移动一步 nx, ny = self.x, self.y if self.direction == 0: ny += 1 elif self.direction == 1: nx += 1 elif self.direction == 2: ny -= 1 else: nx -= 1 # 检查是否越界 if 0 <= nx < self.width and 0 <= ny < self.height: self.x, self.y = nx, ny else: # 越界则转向 self.direction = (self.direction + 1) % 4 self._single_step() # 转向后重新尝试移动

2.4 方向字符串处理

将数字方向转换为字符串：

def getDir(self) -> str: dirs = ["North", "East", "South", "West"] return dirs[self.direction]

3. 完整代码实现

将所有部分组合起来：

class Robot: def __init__(self, width: int, height: int): self.width = width self.height = height self.x = 0 self.y = 0 self.direction = 0 # 0:North, 1:East, 2:South, 3:West def step(self, num: int) -> None: perimeter = 2 * (self.width + self.height) - 4 num %= perimeter if num == 0 and (self.x, self.y) == (0, 0): self.direction = 3 for _ in range(num): self._single_step() def _single_step(self): nx, ny = self.x, self.y if self.direction == 0: ny += 1 elif self.direction == 1: nx += 1 elif self.direction == 2: ny -= 1 else: nx -= 1 if 0 <= nx < self.width and 0 <= ny < self.height: self.x, self.y = nx, ny else: self.direction = (self.direction + 1) % 4 self._single_step() def getPos(self) -> List[int]: return [self.x, self.y] def getDir(self) -> str: dirs = ["North", "East", "South", "West"] return dirs[self.direction]

4. 测试用例与边界条件

4.1 基本测试用例

robot = Robot(6, 3) robot.step(2) print(robot.getPos()) # [2, 0] print(robot.getDir()) # "East" robot.step(2) print(robot.getPos()) # [4, 0] print(robot.getDir()) # "East" robot.step(2) print(robot.getPos()) # [5, 1] print(robot.getDir()) # "North"

4.2 边界条件测试

1. 最小网格测试：

   robot = Robot(1, 1) robot.step(1) print(robot.getPos()) # [0, 0] print(robot.getDir()) # "West" (特殊转向)

2. 大步数测试：

   robot = Robot(5, 5) robot.step(1000000000) # 应该与移动(1000000000 % 16)步的结果相同

3. 角落转向测试：

   robot = Robot(3, 3) robot.step(4) print(robot.getPos()) # [1, 0] print(robot.getDir()) # "South"

5. 复杂度分析与优化

5.1 时间复杂度

• 初始化：O(1)
• step()方法：
  • 优化前：O(num)
  • 优化后：O(perimeter) = O(width + height)
• getPos()和getDir()：O(1)

5.2 空间复杂度

仅存储固定数量的变量，空间复杂度为O(1)

5.3 进一步优化思路

1. 预计算周期：可以预先计算完整移动一个周期后的状态变化，进一步减少计算量。

2. 数学推导：完全通过数学计算确定最终位置和方向，避免逐步模拟。这需要更复杂的推导但可以达到O(1)时间复杂度。

6. 常见错误与调试技巧

6.1 常见错误

1. 方向处理错误：

   • 忘记初始方向是北方
   • 转向顺序错误（应该是顺时针：北→东→南→西）

2. 边界条件错误：

   • 角落位置转向逻辑错误
   • 网格尺寸为1时的特殊处理

3. 步数优化错误：

   • 忘记处理num为0的情况
   • 周长计算错误（应该是2*(w+h)-4）

6.2 调试技巧

1. 小规模测试：先用2x2, 3x3等小网格测试，容易验证逻辑。

2. 打印轨迹：在step()方法中添加打印语句，记录每一步的位置和方向。

3. 可视化工具：可以简单绘制网格和机器人移动路径，直观检查问题。

7. 类似题目推荐

1. LeetCode 874. 模拟行走机器人：

   • 更简单的版本，没有转向要求
   • 重点考察障碍物处理

2. LeetCode 489. 扫地机器人：

   • 需要实现自动清扫算法
   • 涉及DFS/BFS等搜索算法

3. LeetCode 65. 有效数字：

   • 看似不同，但同样需要处理各种边界条件
   • 锻炼严谨的编程思维

4. LeetCode 200. 岛屿数量：

   • 网格遍历的经典题目
   • 可以巩固二维空间处理能力

8. 个人解题心得

这道题我最初提交时也遇到了几个坑：

1. 大数超时：第一次没有做步数优化，直接模拟每一步，导致大数测试用例超时。这提醒我在处理模拟类题目时，一定要先考虑是否有数学优化空间。

2. 方向处理：最初使用字符串直接存储方向，转向时处理起来很麻烦。后来改用数字表示方向，模运算处理转向，代码简洁了很多。

3. 边界条件：特别是当网格尺寸为1x1时，机器人无法移动但方向会变化，这个特殊情况很容易遗漏。

实用技巧：在解决这类模拟题时，建议先在纸上画出几个小例子，手动模拟过程，这样可以更直观地发现潜在问题。