哈希算法题目：模拟行走机器人

字数 2732 2025-10-29 11:32:03

哈希算法题目：模拟行走机器人

题目描述
一个机器人在无限大的网格上行走，从原点 (0,0) 出发，面朝北。它接收一系列指令命令，-2 表示向左转 90 度，-1 表示向右转 90 度，1 <= k <= 9 表示向前移动 k 个单位距离。在行走过程中，网格上有一些障碍物，当机器人试图移动到障碍物所在格子时，它将停在障碍物前一个格子，并继续执行后续指令。请计算机器人执行完所有指令后，从原点到其所在位置的最大欧式距离的平方（即 x^2 + y^2）。

解题过程

问题理解与抽象
- 核心目标：模拟机器人移动过程，并跟踪其位置，最终计算最大距离平方。
- 关键点：
  - 方向处理：机器人有四个方向（北、东、南、西）。转向操作改变的是方向，而不是直接改变坐标。
  - 障碍物处理：这是本题的核心难点。机器人移动时不是“瞬移”到目标点，而是一步一步移动。如果在移动路径上遇到障碍物，它必须立即停止在障碍物之前。
- 输入输出：
  - 输入：commands (指令数组，如 [4,-1,4,-2,4])，obstacles (障碍物坐标列表，如 [[2,4]])。
  - 输出：执行所有指令过程中，机器人到达过的所有位置中，离原点(0,0)最大距离的平方。
数据结构选择：为什么用哈希集合？
- 需求：在机器人移动的每一步（或者说，在判断每一步是否可移动时），我们需要快速判断目标格子是否是一个障碍物。
- 解决方案：将障碍物坐标列表 obstacles 存储在一个哈希集合中。
- 优势：哈希集合提供了 O(1) 时间复杂度的查找操作。相比于在列表 obstacles 中线性扫描（O(n)），使用哈希集合能极大提高判断效率，尤其是在障碍物数量多、移动步数多的情况下。
- 实现细节：由于集合中的元素需要是可哈希的，我们将每个障碍物的坐标 (x, y) 作为一个元组存储在集合中。
方向表示法
- 我们用一个长度为4的数组（或元组）来表示四个方向。约定：
  - 索引 0：北 (North)，移动向量为 (0, 1)
  - 索引 1：东 (East)，移动向量为 (1, 0)
  - 索引 2：南 (South)，移动向量为 (0, -1)
  - 索引 3：西 (West)，移动向量为 (-1, 0)
- 我们用一个变量 dir_index (初始为0，面向北) 来记录当前方向。
- 转向操作：
  - -2 (左转)：相当于逆时针转90度。dir_index = (dir_index - 1) % 4。注意处理负数：(dir_index + 3) % 4 是更稳妥的写法。
  - -1 (右转)：相当于顺时针转90度。dir_index = (dir_index + 1) % 4。
模拟流程（逐步分解）
- 初始化：
  - 当前位置 x = 0, y = 0。
  - 当前方向 dir_index = 0 (北)。
  - 最大距离平方 max_distance_sq = 0。
  - 创建障碍物哈希集合 obstacle_set = set(map(tuple, obstacles))。
- 遍历指令数组 commands：
  - 如果指令是转向 (-1 或 -2)：
    - 根据指令更新 dir_index。
    - 这个指令不改变位置，直接处理下一条指令。
  - 如果指令是移动 (k， 1<=k<=9)：
    - 获取当前方向的移动向量 (dx, dy) = directions[dir_index]。
    - 一步一步移动：重复 k 次。
      - 计算下一步的坐标 next_x = x + dx, next_y = y + dy。
      - 检查障碍物：查询 (next_x, next_y) 是否在 obstacle_set 中。
        
        如果是障碍物：立即停止本次移动（跳出这个 k 次循环）。机器人停在当前位置 (x, y)。
        
        如果不是障碍物：安全移动。更新当前位置 x = next_x, y = next_y。
      - 在移动到的每一个新位置，计算当前距离平方 current_distance_sq = x*x + y*y，并更新 max_distance_sq = max(max_distance_sq, current_distance_sq)。
核心逻辑总结
模拟的关键在于，对于移动指令，不是一次性将机器人从 (x, y) 移动到 (x + k*dx, y + k*dy)，而是沿着移动路径，一小步一小步地移动。每移动一小步，就立即检查下一步的目标格子是否是障碍物。这种“渐进式”移动是正确处理障碍物的核心。
示例演示
指令：commands = [4,-1,4,-2,4], 障碍物：obstacles = [[2,4]]
- 初始化: (x,y)=(0,0), dir_index=0(北), max_sq=0。障碍物集合: {(2,4)}。
- 指令 4 (向北移动4步)：
  - 方向向量 (0,1)。
  - 第1步：下一步(0,1)不在障碍物集，移动。(x,y)=(0,1), max_sq=max(0,1)=1。
  - 第2步：下一步(0,2)不在障碍物集，移动。(x,y)=(0,2), max_sq=max(1,4)=4。
  - 第3步：下一步(0,3)不在障碍物集，移动。(x,y)=(0,3), max_sq=max(4,9)=9。
  - 第4步：下一步(0,4)不在障碍物集，移动。(x,y)=(0,4), max_sq=max(9,16)=16。
- 指令 -1 (右转)：dir_index = (0+1)%4 = 1 (东)。
- 指令 4 (向东移动4步)：
  - 方向向量 (1,0)。
  - 第1步：下一步(1,4)不在障碍物集，移动。(x,y)=(1,4), max_sq=max(16,17)=17。
  - 第2步：下一步(2,4) 在障碍物集中！停止移动。机器人停在(1,4)。
- 指令 -2 (左转)：dir_index = (1+3)%4 = 0 (北)。
- 指令 4 (向北移动4步)：
  - 方向向量 (0,1)。
  - 第1步：下一步(1,5)不在障碍物集，移动。(x,y)=(1,5), max_sq=max(17,26)=26。
  - ... 后续步骤无障碍，最终位置(1,5)，max_sq=26。
- 结果：26。

通过以上细致的步骤，我们利用哈希集合高效处理了障碍物判断，并通过逐步模拟准确地处理了机器人的移动和转向，最终得到了正确的结果。

哈希算法题目：模拟行走机器人题目描述一个机器人在无限大的网格上行走，从原点 (0,0) 出发，面朝北。它接收一系列指令命令，-2 表示向左转 90 度，-1 表示向右转 90 度，1 <= k <= 9 表示向前移动 k 个单位距离。在行走过程中，网格上有一些障碍物，当机器人试图移动到障碍物所在格子时，它将停在障碍物前一个格子，并继续执行后续指令。请计算机器人执行完所有指令后，从原点到其所在位置的最大欧式距离的平方（即 x^2 + y^2 ）。解题过程问题理解与抽象核心目标：模拟机器人移动过程，并跟踪其位置，最终计算最大距离平方。关键点：方向处理：机器人有四个方向（北、东、南、西）。转向操作改变的是方向，而不是直接改变坐标。障碍物处理：这是本题的核心难点。机器人移动时不是“瞬移”到目标点，而是一步一步移动。如果在移动路径上遇到障碍物，它必须立即停止在障碍物之前。输入输出：输入： commands (指令数组，如 [4,-1,4,-2,4] )， obstacles (障碍物坐标列表，如 [[2,4]] )。输出：执行所有指令过程中，机器人到达过的所有位置中，离原点(0,0)最大距离的平方。数据结构选择：为什么用哈希集合？需求：在机器人移动的每一步（或者说，在判断每一步是否可移动时），我们需要快速判断目标格子是否是一个障碍物。解决方案：将障碍物坐标列表 obstacles 存储在一个哈希集合中。优势：哈希集合提供了 O(1) 时间复杂度的查找操作。相比于在列表 obstacles 中线性扫描（O(n)），使用哈希集合能极大提高判断效率，尤其是在障碍物数量多、移动步数多的情况下。实现细节：由于集合中的元素需要是可哈希的，我们将每个障碍物的坐标 (x, y) 作为一个元组存储在集合中。方向表示法我们用一个长度为4的数组（或元组）来表示四个方向。约定：索引 0：北 (North)，移动向量为 (0, 1) 索引 1：东 (East)，移动向量为 (1, 0) 索引 2：南 (South)，移动向量为 (0, -1) 索引 3：西 (West)，移动向量为 (-1, 0) 我们用一个变量 dir_index (初始为0，面向北) 来记录当前方向。转向操作： -2 (左转)：相当于逆时针转90度。 dir_index = (dir_index - 1) % 4 。注意处理负数： (dir_index + 3) % 4 是更稳妥的写法。 -1 (右转)：相当于顺时针转90度。 dir_index = (dir_index + 1) % 4 。模拟流程（逐步分解）初始化：当前位置 x = 0 , y = 0 。当前方向 dir_index = 0 (北)。最大距离平方 max_distance_sq = 0 。创建障碍物哈希集合 obstacle_set = set(map(tuple, obstacles)) 。遍历指令数组 commands ：如果指令是转向 ( -1 或 -2 ) ：根据指令更新 dir_index 。这个指令不改变位置，直接处理下一条指令。如果指令是移动 ( k ， 1<=k<=9) ：获取当前方向的移动向量 (dx, dy) = directions[dir_index] 。一步一步移动：重复 k 次。计算下一步的坐标 next_x = x + dx , next_y = y + dy 。检查障碍物：查询 (next_x, next_y) 是否在 obstacle_set 中。如果是障碍物：立即停止本次移动（跳出这个 k 次循环）。机器人停在当前位置 (x, y) 。如果不是障碍物：安全移动。更新当前位置 x = next_x , y = next_y 。在移动到的每一个新位置，计算当前距离平方 current_distance_sq = x*x + y*y ，并更新 max_distance_sq = max(max_distance_sq, current_distance_sq) 。核心逻辑总结模拟的关键在于，对于移动指令，不是一次性将机器人从 (x, y) 移动到 (x + k*dx, y + k*dy) ，而是沿着移动路径，一小步一小步地移动。每移动一小步，就立即检查下一步的目标格子是否是障碍物。这种“渐进式”移动是正确处理障碍物的核心。示例演示指令： commands = [4,-1,4,-2,4] , 障碍物： obstacles = [[2,4]] 初始化: (x,y)=(0,0) , dir_index=0 (北), max_sq=0 。障碍物集合: {(2,4)} 。指令 4 (向北移动4步)：方向向量 (0,1) 。第1步：下一步(0,1)不在障碍物集，移动。 (x,y)=(0,1) , max_sq=max(0,1)=1 。第2步：下一步(0,2)不在障碍物集，移动。 (x,y)=(0,2) , max_sq=max(1,4)=4 。第3步：下一步(0,3)不在障碍物集，移动。 (x,y)=(0,3) , max_sq=max(4,9)=9 。第4步：下一步(0,4)不在障碍物集，移动。 (x,y)=(0,4) , max_sq=max(9,16)=16 。指令 -1 (右转)： dir_index = (0+1)%4 = 1 (东)。指令 4 (向东移动4步)：方向向量 (1,0) 。第1步：下一步(1,4)不在障碍物集，移动。 (x,y)=(1,4) , max_sq=max(16,17)=17 。第2步：下一步(2,4) 在障碍物集中！停止移动。机器人停在(1,4)。指令 -2 (左转)： dir_index = (1+3)%4 = 0 (北)。指令 4 (向北移动4步)：方向向量 (0,1) 。第1步：下一步(1,5)不在障碍物集，移动。 (x,y)=(1,5) , max_sq=max(17,26)=26 。 ... 后续步骤无障碍，最终位置(1,5)， max_sq=26 。结果：26。通过以上细致的步骤，我们利用哈希集合高效处理了障碍物判断，并通过逐步模拟准确地处理了机器人的移动和转向，最终得到了正确的结果。