Medium

题目描述

机器人在一个无限的 XY 平面上行走，从点 (0, 0) 开始，面朝北方。机器人可以接收以下三种类型的指令：

  • -2：向左转 90 度
  • -1：向右转 90 度
  • 1 <= k <= 9：向前行走 k 个单位，每次一个单位

在网格上的一些方格子是障碍物。第 i 个障碍物位于网格点 obstacles[i] = (xi, yi)。如果机器人碰到障碍物，它将停留在当前位置（障碍物旁边的方格），然后继续执行下一个指令。

返回从原点出发，机器人在其路径中到达的最大欧几里得距离的平方（即，如果距离为 5，则返回 25）。

注意：

  • (0, 0) 处可能有障碍物。如果是这样，机器人将忽略障碍物，直到它离开原点。但是，由于障碍物的存在，它将无法返回到 (0, 0)。
  • 北表示 +Y 方向
  • 东表示 +X 方向
  • 南表示 -Y 方向
  • 西表示 -X 方向

示例 1：

输入：commands = [4,-1,3], obstacles = []
输出：25
解释：机器人从 (0, 0) 开始：
向北移动 4 个单位到 (0, 4)
向右转
向东移动 3 个单位到 (3, 4)
距离原点最远的点是 (3, 4)，距离平方为 3² + 4² = 25

示例 2：

输入：commands = [4,-1,4,-2,4], obstacles = [[2,4]]
输出：65

示例 3：

输入：commands = [6,-1,-1,6], obstacles = [[0,0]]
输出：36

约束条件：

  • 1 <= commands.length <= 10⁴
  • commands[i] 是 -2、-1 或范围 [1, 9] 内的整数
  • 0 <= obstacles.length <= 10⁴
  • -3 * 10⁴ <= xi, yi <= 3 * 10⁴

解题思路

这道题是一个典型的模拟题，需要按照给定指令模拟机器人的移动过程。

核心思路：

  1. 方向表示：用数组表示四个方向（北、东、南、西），方便进行方向转换
  2. 障碍物存储：使用哈希集合存储障碍物坐标，实现 O(1) 查询
  3. 逐步移动：对于移动指令，需要逐步移动而不是直接跳跃，确保能及时检测障碍物
  4. 距离追踪：在每次移动后更新最大距离平方

具体实现：

  • 使用方向数组 dirs = [[0,1], [1,0], [0,-1], [-1,0]] 分别表示北、东、南、西
  • 用变量 d 记录当前方向（0-3）
  • 转向操作：左转 d = (d + 3) % 4，右转 d = (d + 1) % 4
  • 移动时逐步检查每个位置是否有障碍物

时间复杂度分析：

  • 障碍物转换为集合：O(obstacles.length)
  • 处理所有指令：O(sum of all move distances)
  • 总体：O(obstacles.length + N)，其中 N 是总移动步数

这种方法简洁高效，避免了复杂的几何计算。

代码实现

class Solution {
public:
    int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
        // 方向数组：北、东、南、西
        vector<vector<int>> dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int d = 0; // 当前方向，0=北，1=东，2=南，3=西
        
        // 将障碍物存入set以便快速查找
        set<pair<int, int>> obstacleSet;
        for (auto& obstacle : obstacles) {
            obstacleSet.insert({obstacle[0], obstacle[1]});
        }
        
        int x = 0, y = 0; // 当前位置
        int maxDist = 0;
        
        for (int command : commands) {
            if (command == -2) {
                // 左转90度
                d = (d + 3) % 4;
            } else if (command == -1) {
                // 右转90度
                d = (d + 1) % 4;
            } else {
                // 向前移动command步
                for (int i = 0; i < command; i++) {
                    int nx = x + dirs[d][0];
                    int ny = y + dirs[d][1];
                    
                    // 检查下一步是否有障碍物
                    if (obstacleSet.find({nx, ny}) == obstacleSet.end()) {
                        x = nx;
                        y = ny;
                        maxDist = max(maxDist, x * x + y * y);
                    } else {
                        break; // 遇到障碍物停止移动
                    }
                }
            }
        }
        
        return maxDist;
    }
};

class Solution:
    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
        # 方向数组：北、东、南、西
        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        d = 0  # 当前方向，0=北，1=东，2=南，3=西
        
        # 将障碍物存入set以便快速查找
        obstacle_set = set(map(tuple, obstacles))
        
        x, y = 0, 0  # 当前位置
        max_dist = 0
        
        for command in commands:
            if command == -2:
                # 左转90度
                d = (d + 3) % 4
            elif command == -1:
                # 右转90度
                d = (d + 1) % 4
            else:
                # 向前移动command步
                for _ in range(command):
                    nx, ny = x + dirs[d][0], y + dirs[d][1]
                    
                    # 检查下一步是否有障碍物
                    if (nx, ny) not in obstacle_set:
                        x, y = nx, ny
                        max_dist = max(max_dist, x * x + y * y)
                    else:
                        break  # 遇到障碍物停止移动
        
        return max_dist

public class Solution {
    public int RobotSim(int[] commands, int[][] obstacles) {
        // 方向数组：北、东、南、西
        int[,] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int d = 0; // 当前方向，0=北，1=东，2=南，3=西
        
        // 将障碍物存入HashSet以便快速查找
        HashSet<string> obstacleSet = new HashSet<string>();
        foreach (var obstacle in obstacles) {
            obstacleSet.Add(obstacle[0] + "," + obstacle[1]);
        }
        
        int x = 0, y = 0; // 当前位置
        int maxDist = 0;
        
        foreach (int command in commands) {
            if (command == -2) {
                // 左转90度
                d = (d + 3) % 4;
            } else if (command == -1) {
                // 右转90度
                d = (d + 1) % 4;
            } else {
                // 向前移动command步
                for (int i = 0; i < command; i++) {
                    int nx = x + dirs[d, 0];
                    int ny = y + dirs[d, 1];
                    
                    // 检查下一步是否有障碍物
                    if (!obstacleSet.Contains(nx + "," + ny)) {
                        x = nx;
                        y = ny;
                        maxDist = Math.Max(maxDist, x * x + y * y);
                    } else {
                        break; // 遇到障碍物停止移动
                    }
                }
            }
        }
        
        return maxDist;
    }
}

var robotSim = function(commands, obstacles) {
    let x = 0, y = 0;
    let direction = 0; // 0: North, 1: East, 2: South, 3: West
    let maxDistSq = 0;
    
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    const obstacleSet = new Set(obstacles.map(obs => obs[0] + ',' + obs[1]));
    
    for (let command of commands) {
        if (command === -2) {
            direction = (direction + 3) % 4;
        } else if (command === -1) {
            direction = (direction + 1) % 4;
        } else {
            const [dx, dy] = directions[direction];
            for (let i = 0; i < command; i++) {
                const newX = x + dx;
                const newY = y + dy;
                if (!obstacleSet.has(newX + ',' + newY)) {
                    x = newX;
                    y = newY;
                    maxDistSq = Math.max(maxDistSq, x * x + y * y);
                } else {
                    break;
                }
            }
        }
    }
    
    return maxDistSq;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(obstacles.length + N)，其中 N 是所有移动指令的总步数。障碍物转换为集合需要 O(obstacles.length)，处理所有移动需要 O(N)
空间复杂度O(obstacles.length)，用于存储障碍物坐标的哈希集合

相关题目