模拟行走机器人 图解题解

这道题到底在问什么

输入

commands=[4,-1,3], obstacles=[]

输出

25 （走到 [3,4]，3²+4²=25）

输入

commands=[4,-1,4,-2,4], obstacles=[[2,4]]

输出

65 （被障碍挡后绕到 [1,8]）

最优解：一步一步想明白

1. 3记住这套「转向改下标、前进逐格查障碍、每步刷新最远距离平方」，下面每一帧都在套它。
2. 4开局：机器人在原点 [0,0]（紫色箭头朝北 ↑），红色 ▦ 是障碍 [2,3]。最远距离平方 ans 先记 0，下面开始读指令。
3. 5先认舞台：横向是 x（向右增大、即东，◎ 标的就是右边一格），纵向是 y（向上增大、即北）。四个朝向按「北 东 南 西」排成一圈，机器人现在朝北，右转顺时针挪一格、左转逆时针挪一格。
4. 6第 1 条指令是 3，朝 北 ↑ 前进 3 步，一步步走。第 1 步：先探前方一格 [0,1]（◎ 标记），查它在不在障碍集合里，再决定走不走。
5. 7前方没障碍，真走过去，到达 [0,1]。算一下 dist² = 0² + 1² = 1，比旧的最远还大，刷新 ans = 1。
6. 8第 2 步：先探前方一格 [0,2]（◎ 标记），查它在不在障碍集合里，再决定走不走。
7. 9前方没障碍，真走过去，到达 [0,2]。算一下 dist² = 0² + 2² = 4，比旧的最远还大，刷新 ans = 4。
8. 10第 3 步：先探前方一格 [0,3]（◎ 标记），查它在不在障碍集合里，再决定走不走。
9. 11前方没障碍，真走过去，到达 [0,3]。算一下 dist² = 0² + 3² = 9，比旧的最远还大，刷新 ans = 9。
10. 12第 2 条指令是 -1，右转 90 度。朝向从 北 ↑ 转到 东 →（箭头跟着转），下标 k 往后挪一格。机器人原地不动，ans 仍是 9。
11. 13第 3 条指令是 2，朝 东 → 前进 2 步，一步步走。第 1 步：先探前方一格 [1,3]（◎ 标记），查它在不在障碍集合里，再决定走不走。
12. 14前方没障碍，真走过去，到达 [1,3]。算一下 dist² = 1² + 3² = 10，比旧的最远还大，刷新 ans = 10。
13. 15第 2 步：先探前方一格 [2,3]（◎ 标记），查它在不在障碍集合里，再决定走不走。
14. 16前方 [2,3] 是障碍 ▦，走不过去。机器人停在 [1,3] 不动，这条指令剩下的步数全部作废，直接去下一条指令。ans 保持 10。
15. 17第 4 条指令是 -2，左转 90 度。朝向从 东 → 转到 北 ↑（箭头跟着转），下标 k 往回挪一格（加 3 再对 4 取模）。机器人没移动，ans 还是 10。
16. 18第 5 条指令是 1，朝 北 ↑ 前进 1 步，一步步走。第 1 步：先探前方一格 [1,4]（◎ 标记），查它在不在障碍集合里，再决定走不走。
17. 19前方没障碍，真走过去，到达 [1,4]。算一下 dist² = 1² + 4² = 17，比旧的最远还大，刷新 ans = 17。
18. 20全程走完，机器人最后停在 [1,4]。一路上离原点最远的那一刻就在这里，dist² = 1² + 4² = 17，这就是答案 17。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

#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;
    }
};

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;
    }
}

复杂度

面试官可能追问