LeetCode 874. 模拟行走机器人

约 6 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节
标签
数组 哈希表 模拟

题目描述

✅ 874. 模拟行走机器人

image-20260928225239533

image-20260928225239534

image-20260928225239535

题意分析

机器人从原点面向北，逐条执行左转、右转和前进指令。前进途中若下一格有障碍，就停在当前格并放弃本条指令的剩余步数，之后继续执行下一条指令。答案是整个行走过程中到原点的最大距离平方，不只看最终位置。

解法：哈希集合 + 模拟

核心思路

[!blue]

保存当前坐标 (x, y) 和方向下标 dir，方向按北、东、南、西排列，对应位移 (0,1)、(1,0)、(0,-1)、(-1,0)。右转沿顺序前进一格，使用 (dir + 1) % 4；左转退一格，写成 (dir + 3) % 4 可避免负下标。

将障碍坐标放入哈希集合，前进时先根据方向计算下一格 (nx, ny)，确认没有障碍才更新当前位置。单条指令最多走 9 步，直接逐格检查即可，也能发现途中障碍；若只检查整条指令的终点，就可能穿过障碍。

代码把坐标对编码为一个 64 位整数：x 的 32 位放在高半部分，y 的 32 位放在低半部分。对 y 做掩码或转为 uint32，是为了保留它的低 32 位且避免负数符号扩展污染高位。两部分互不重叠，能够唯一还原两个坐标，负坐标也不会发生键冲突。

每次成功移动后，用 x*x + y*y 更新最大值；初始原点的距离为 0，转向和遇障碍都不改变位置。只检查即将进入的格子，也自然满足原点有障碍的规则：机器人仍能从原点离开，但之后不能再次走回原点。

解题步骤

  1. 编码全部障碍并放入集合，初始化坐标、朝北方向和最大距离平方。
  2. 遇到 -2 左转，遇到 -1 右转，两者都只更新方向。
  3. 正数指令逐步计算下一格；若该格在障碍集合中，跳出本次前进循环，否则更新位置与最大距离平方。
  4. 全部指令处理完后返回最大值。题目保证答案小于 $2^{31}$，距离平方可用现有整数类型保存。

代码实现

class Solution {
    public int robotSim(int[] commands, int[][] obstacles) {
        Set<Long> block = new HashSet<>();

        for (int[] o : obstacles) {
            long key = (((long) o[0]) << 32) ^ (o[1] & 0xffffffffL);

            block.add(key);
        }

        int[][] dirs = new int[4][2];

        dirs[0] = new int[] {
            0,
            1
        };
        dirs[1] = new int[] {
            1,
            0
        };
        dirs[2] = new int[] {
            0,
            -1
        };
        dirs[3] = new int[] {
            -1,
            0
        };
        int dir = 0;
        int x = 0;
        int y = 0;
        int best = 0;

        for (int cmd : commands) {
            if (cmd == -2) {
                dir = (dir + 3) % 4;
            } else if (cmd == -1) {
                dir = (dir + 1) % 4;
            } else {
                for (int i = 0; i < cmd; i++) {
                    int nx = x + dirs[dir][0];
                    int ny = y + dirs[dir][1];
                    long key = (((long) nx) << 32) ^ (ny & 0xffffffffL);

                    // 检查即将进入的格子，障碍只中止当前前进指令
                    if (block.contains(key)) {
                        break;
                    }

                    x = nx;
                    y = ny;
                    best = Math.max(best, x * x + y * y);
                }
            }
        }

        return best;
    }
}

func robotSim(commands []int, obstacles [][]int) int {
    block := make(map[int64]bool)
    for _, o := range obstacles {
        key := (int64(o[0]) << 32) ^ int64(uint32(o[1]))
        block[key] = true
    }

    dirs := make([][2]int, 0, 4)
    dirs = append(dirs,
        [2]int{
            0,
            1,
        },
        [2]int{
            1,
            0,
        },
        [2]int{
            0,
            -1,
        },
        [2]int{
            -1,
            0,
        },
    )
    dir := 0
    x, y := 0, 0
    best := 0

    for _, cmd := range commands {
        if cmd == -2 {
            dir = (dir + 3) % 4
        } else if cmd == -1 {
            dir = (dir + 1) % 4
        } else {
            for step := 0; step < cmd; step++ {
                nx := x + dirs[dir][0]
                ny := y + dirs[dir][1]
                key := (int64(nx) << 32) ^ int64(uint32(ny))
                // 检查即将进入的格子，障碍只中止当前前进指令
                if block[key] {
                    break
                }
                x, y = nx, ny
                dist := x*x + y*y
                if dist > best {
                    best = dist
                }
            }
        }
    }

    return best
}

复杂度分析

  • 时间复杂度：期望 $O(M+C)$，其中 $M$ 为障碍数、$C$ 为指令数。建集合耗时 $O(M)$，每条指令最多尝试 9 次移动，查询障碍的期望时间为常数。
  • 空间复杂度：$O(M)$，用于障碍集合，坐标和方向只占常数空间。

关键点总结

[!green]

  • 障碍判断针对候选下一格。
  • 坐标编码需要区分两个分量并支持负数。

易错点总结

[!yellow]

  • 命中障碍后结束全部指令，会漏掉后面的转向和移动。
  • 只返回最终位置距离，可能漏掉早先走到的更远点。
  • 把当前格当作障碍检查对象，会先走进障碍。

相似题目

题目 难度 关联与区别
1496. 判断路径是否相交 简单 同样按方向在整数网格中移动，原题检测访问重复，本题用固定障碍集合阻止前进。
2069. 模拟行走机器人 II 中等 原题只沿矩形外边行走，可按周长压缩步数，本题有任意障碍，需要判断路径是否受阻。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/37730531
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！