模拟行走机器人 图解题解

机器人在网格上按指令走，最后要返回什么

机器人从 [0,0] 出发、面朝北，读一串 commands：-2 左转 90 度，-1 右转 90 度，正数 x 朝当前方向前进 x 步；途中撞障碍就停在原地、该指令剩余步数作废。要返回一路离原点最远那刻的欧氏距离平方。题面 commands=[4,-1,4,-2,4]、obstacles=[[2,4]] 时答案 65。

障碍逐个比对，为什么步数一多就拖垮

前进时每走一格都要先答「下一格是不是障碍」。若把障碍堆成列表、每步拿坐标逐个比对，前进步数和障碍数都可能上万，最坏是步数乘障碍数次比较，规模一大就拖垮。这每步都问的查询，得压到常数时间。

转向、查挡、记距离，这道题就三件事各管一段

先说转向。北、东、南、西按顺时针排成一圈，用下标 k 指当前朝向：右转（-1）让 k 加 1、左转（-2）让 k 加 3、都对 4 取模——下标转满一圈就回到 0，这就是对 4 取模；加 3 即往回退一格，用加法绕开负数取模。再配方向数组 dirs=(0,1,0,-1,0)，位移取 (dirs[k], dirs[k+1])，下标 0 朝北、1 朝东，往下是南、西。

查挡靠哈希集合：障碍坐标 (x,y) 全塞进集合，只管在不在、平均查询 O(1)，前进前算出下一格、问它在不在集合里。记平方而非距离，是因欧氏距离要开平方根、会引浮点误差，而只比谁更远时平方与距离顺序一致，索性存 x²+y²、既是答案又免开方。

转向改下标、前进逐格探，一步一刷新最远值

主循环逐条读指令。遇 -2 或 -1 只动下标 k，人不挪、最远值不变。遇正数 x 就重复 x 次：按朝向算出下一格、查集合是不是障碍；是就立刻停、跳出这条剩余步数；不是才走过去更新坐标，并马上用 x²+y² 和已记最远值取大。关键在「马上」：最远点可能就在撞墙前那步，走完整条再算就漏了。

[4,-1,4,-2,4]、障碍 [2,4] 一步步走到 65

起点 [0,0] 朝北，ans=0，集合只有 (2,4)。第一条 4：朝北走 4 步，依次到 [0,1]、[0,2]、[0,3]、[0,4]，ans 刷成 1、4、9、16。第二条 -1：右转，北转东，人不动，ans 仍 16。

第三条 4：朝东走。第一步到 [1,4]，ans=1²+4²=17；第二步下一格 [2,4] 是障碍，停在 [1,4]、剩 3 步作废，ans 保持 17。第四条 -2：左转回北。第五条 4：朝北走 4 步经 [1,5]、[1,6]、[1,7] 到 [1,8]，ans 依次刷成 26、37、50、65，终点即最远，答案 65。

-2 和 -1 记反，整条路线跟着偏到别处

最常见的错是把 -2 当右转、-1 当左转，方向一反、之后位移全错，记牢 -2 左、-1 右。撞障碍别把后面指令全丢，作废的只这条前进，人停原地、后续照常执行，绕过后可能走更远。还有个隐蔽的：走完整条才算距离，漏掉半路被挡时更靠外的落点。

复杂度：n 条指令扫一遍、前进总步数记作 k、每步查障碍 O(1)，时间 O(n+k)；空间在障碍集合、O(m)。全是转向没前进时人在原点、答案 0；第一条前进第一格就撞障碍、没迈一步，同样 0。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
        dirs = (0, 1, 0, -1, 0)
        s = {(x, y) for x, y in obstacles}
        ans = k = 0
        x = y = 0
        for c in commands:
            if c == -2:
                k = (k + 3) % 4
            elif c == -1:
                k = (k + 1) % 4
            else:
                for _ in range(c):
                    nx, ny = x + dirs[k], y + dirs[k + 1]
                    if (nx, ny) in s:
                        break
                    x, y = nx, ny
                    ans = max(ans, x * x + y * y)
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
        int dirs[5] = {0, 1, 0, -1, 0};
        auto f = [](int x, int y) {
            return x * 60010 + y;
        };
        unordered_set<int> s;
        for (auto& e : obstacles) {
            s.insert(f(e[0], e[1]));
        }
        int ans = 0, k = 0;
        int x = 0, y = 0;
        for (int c : commands) {
            if (c == -2) {
                k = (k + 3) % 4;
            } else if (c == -1) {
                k = (k + 1) % 4;
            } else {
                while (c--) {
                    int nx = x + dirs[k], ny = y + dirs[k + 1];
                    if (s.count(f(nx, ny))) {
                        break;
                    }
                    x = nx;
                    y = ny;
                    ans = max(ans, x * x + y * y);
                }
            }
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int robotSim(int[] commands, int[][] obstacles) {
        int[] dirs = {0, 1, 0, -1, 0};
        Set<Integer> s = new HashSet<>(obstacles.length);
        for (int[] e : obstacles) {
            s.add(f(e[0], e[1]));
        }
        int ans = 0, k = 0;
        int x = 0, y = 0;
        for (int c : commands) {
            if (c == -2) {
                k = (k + 3) % 4;
            } else if (c == -1) {
                k = (k + 1) % 4;
            } else {
                while (c-- > 0) {
                    int nx = x + dirs[k], ny = y + dirs[k + 1];
                    if (s.contains(f(nx, ny))) {
                        break;
                    }
                    x = nx;
                    y = ny;
                    ans = Math.max(ans, x * x + y * y);
                }
            }
        }
        return ans;
    }

    private int f(int x, int y) {
        return x * 60010 + y;
    }
}