LeetCode 1041. 困于环中的机器人

2024-01-08 HGNULB 约 9 分钟

文章信息 7 个分类 3 个标签

分类

题目描述

✅ 1041. 困于环中的机器人

题意分析

机器人站在无限大平面的原点，初始朝北，手上有一串只含 G、L、R 的指令：G 表示朝当前朝向前进一格，L 表示原地左转九十度，R 表示原地右转九十度。这串指令会被无限次重复执行，要判断机器人的轨迹是否被限制在某个有限半径的圆内。

这里最容易读错的是「困于环中」四个字。它并不要求轨迹是一个圆形，也不要求机器人回到原点，只要求整条无限长的轨迹不会跑到无穷远处，也就是所有到过的坐标被某个有限的边界框住。

约束给出的信号很关键：指令长度不超过 100，只有三种字符，而且没有任何随机性——同一串指令每次执行的效果完全一致。这说明整个系统是确定性的，一轮指令对机器人状态（位置加朝向）的作用是一个固定的变换，重复执行就是把这个变换反复复合。规模这么小，说明题目考的不是效率，而是能否看出「只需要模拟一轮」这个结论。

边界方面要注意：指令里可能一个 G 都没有，机器人从头到尾停在原点；也可能全是 G，机器人沿一条直线一去不回；朝向只有四种，转向按九十度为单位，不会出现斜向。

解法：模拟一轮指令

核心思路

直接的想法是把指令重复执行很多轮，看坐标会不会越跑越远。但「很多轮」到底是几轮无法确定，跑得太少可能误判，跑得太多又没有终止条件，这条路走不通。瓶颈在于它把无限行为当成了模拟对象，而不是去分析这个行为的结构。

换个角度：机器人的完整状态是「位置 + 朝向」。执行完一轮指令后，设位置从原点变成了 $(x, y)$，朝向从北变成了某个方向 d。由于系统是确定性的，第二轮会在第一轮的结果之上再施加完全相同的「先旋转到 d，再平移 $(x, y)$」这一变换。于是问题化归为：把同一个「旋转加平移」复合无限次，轨迹会不会发散。

分情况看就清楚了。如果一轮结束后回到了原点，那不管朝向变成什么，机器人的轨迹从第二轮开始就是第一轮的重复（顶多整体旋转了一下），永远出不了第一轮走过的最大半径，一定有界。如果一轮结束后没回原点但朝向变了，那么这个变换含有一个非零角度的旋转分量，四轮之内旋转角必然累计成三百六十度的整数倍，四轮位移向量的和在旋转作用下互相抵消，机器人恰好回到原点，之后开始周期性重复，同样有界。只有既没回到原点、朝向又保持向北这一种情况，每轮都在原方向上叠加同一个非零位移，机器人沿直线匀速远离原点，轨迹无界。

于是不变量可以写成：只需模拟一轮指令，记录终点坐标 $(x, y)$ 和终点朝向 d，则轨迹有界当且仅当 $(x, y)$ 为原点，或者 d 不等于初始朝向。无限的行为被一轮模拟加一个判断彻底刻画。

解题步骤

第一步，初始化 x = 0、y = 0 表示起点在原点，dir = 0 表示初始朝北。把朝向编码成 0 到 3 的整数而不是字符串或枚举，是为了让转向可以用模四加法一步完成。

第二步，准备方向表 dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}，依次代表北、东、南、西。这个顺序不是随意的，它按顺时针排列，使得「右转」恰好对应下标加一、「左转」对应下标减一，方向表的排列顺序本身就编码了转向规则。

第三步，从头到尾扫描指令，遇到 G 就执行 x += dirs[dir][0]、y += dirs[dir][1]。前进量必须取自当前朝向而不是初始朝向，因为之前的转向已经改变了「前方」的含义。

第四步，遇到 L 执行 dir = (dir + 3) % 4。左转是逆时针九十度，在顺时针排列的方向表里相当于下标减一；写成加三取模而不是减一取模，是为了避开负数取模的语言差异——Java 和 Go 的 % 对负数都返回负余数，(0 - 1) % 4 会得到 -1 并导致数组越界。

第五步，遇到 R 执行 dir = (dir + 1) % 4，即顺时针九十度，下标加一，取模保证在 0 到 3 之间循环。

第六步，一轮扫描结束后返回 (x == 0 && y == 0) || dir != 0。前半个条件对应「回到原点」，后半个条件对应「朝向改变」，两者取或正是上面推导出的判定式；两个条件都不满足时，说明机器人朝北直线漂移，返回 false。

以 instructions = "GGLLGG" 走一遍：初始 (0, 0)、dir = 0（北）。第一个 G 走到 (0, 1)；第二个 G 走到 (0, 2)；第一个 L 让 dir 变成 (0 + 3) % 4 = 3（西）；第二个 L 让 dir 变成 (3 + 3) % 4 = 2（南）；第三个字符 G 沿 {0, -1} 走到 (0, 1)；最后一个 G 走到 (0, 0)。一轮结束，坐标回到原点，返回 true——机器人在原地做往返运动，显然有界。再看 instructions = "GG"：两个 G 把机器人送到 (0, 2)，dir 始终为 0。坐标非原点且朝向未变，返回 false——它会一直朝北走下去，轨迹无界。最后看 instructions = "GL"：G 走到 (0, 1)，L 把 dir 变成 3。坐标不是原点，但朝向变了，返回 true——实际上机器人会沿一个边长为 1 的正方形循环，四轮后回到原点。

代码实现

class Solution {
    // 若回到原点，则必在环内。
    public boolean isRobotBounded(String instructions) {
        int x = 0;
        int y = 0;
        int dir = 0;
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

        for (int i = 0; i < instructions.length(); i++) {
            char c = instructions.charAt(i);
            if (c == 'G') {
                x += dirs[dir][0];
                y += dirs[dir][1];
            } else if (c == 'L') {
                dir = (dir + 3) % 4;
            } else {
                dir = (dir + 1) % 4;
            }
        }

        return (x == 0 && y == 0) || dir != 0;
    }
}

func isRobotBounded(instructions string) bool {
    // 若回到原点，则必在环内。
    x, y := 0, 0
    dir := 0
    dirs := [][]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}

    for i := 0; i < len(instructions); i++ {
        c := instructions[i]
        if c == 'G' {
            x += dirs[dir][0]
            y += dirs[dir][1]
        } else if c == 'L' {
            dir = (dir + 3) % 4
        } else {
            dir = (dir + 1) % 4
        }
    }

    return (x == 0 && y == 0) || dir != 0
}

复杂度分析

时间复杂度：$O(n)$，其中 n 为指令长度。指令只被扫描一轮，每个字符对应常数次加法、取模和数组访问，没有嵌套循环也不需要重复执行多轮。

空间复杂度：$O(1)$。只维护坐标、朝向三个整型变量，以及一张固定四行两列的方向表，占用与输入规模无关。

关键点总结

面对「无限重复」的行为，先把一轮的净效果抽象成一个变换，再分析这个变换复合下去会不会发散，这比试图模拟很多轮要可靠得多，也是周期性、循环节类问题的通用切入点。

旋转分量是有界性的关键：只要一轮之后朝向发生了任何改变，四轮之内旋转角必然回到起点且位移互相抵消，「四轮必回原点」这个结论值得单独记住。

方向表的排列顺序应当承载转向语义：按顺时针写好四个方向后，左右转就退化成下标的加减，避免了一大堆分支判断。

用加法代替减法做环形取模：写成 (dir + 3) % 4 而不是 (dir - 1) % 4，可以彻底规避负数取模在不同语言里符号不一致带来的隐患。

面试视角：不要一上来就给判定式，先说清楚「状态 = 位置 + 朝向」这个建模，再分三种情况论证有界性，尤其要主动证明「朝向改变则四轮回原点」这一步；面试官考察的正是能否把无限过程归约成有限分析，而不是能否背下那一行返回语句。

易错点总结

把 L 写成 dir = (dir - 1) % 4：instructions = "L" 时 dir 变成 -1，下一次执行 G 访问 dirs[-1] 直接数组越界。

左右转的方向搞反：instructions = "GL" 若把 L 当成加一，虽然本例仍返回 true，但对 instructions = "GLGLGGLGL" 这类不对称指令会算出错误的终点坐标，进而误判有界性。

只判断是否回到原点：instructions = "GL" 会因为终点是 (0, 1) 而返回 false，但机器人实际沿正方形循环，正确答案是 true。

只判断朝向是否改变：instructions = "GGLLGG" 一轮后朝向是南、坐标是原点，若只看朝向会返回 true，虽然结果碰巧对，但换成 instructions = "LL" 这种朝向变了却原地未动的用例，逻辑上就说不通了，两个条件必须取或。

把判定条件里的「或」写成「与」：instructions = "GL" 因为坐标非原点而整体为假，返回 false，与正确答案相反。

前进时使用初始朝向而不是当前朝向：instructions = "RG" 本应向东走到 (1, 0)，误用初始朝向会算成 (0, 1)，虽然本例结论不变，但对 instructions = "RGGL" 之类会得到完全错误的终点。

试图重复执行多轮再观察坐标：instructions = "GL" 需要整整四轮才回到原点，若只跑两轮就下结论会误判为无界；而对真正无界的输入又永远等不到终止条件。

把「困于环中」理解成轨迹必须是圆形：instructions = "GGLLGG" 的轨迹是一条来回走的线段，并不是圆，但它确实有界，答案是 true。

遍历时用 instructions.charAt(i) 之外的方式却忘了 Go 里字符串按字节索引的差异：本题只含 ASCII 字符所以无碍，但把同样写法搬到含多字节字符的题目上，instructions[i] 会取到半个字符。

朝向初值设成非 0 的值：把 dir 初始化为 1（东）后，最终判断里的 dir != 0 就不再表示「朝向改变」，instructions = "GG" 会被误判为 true。

相似题目

题目	难度	考察点
54. 螺旋矩阵	中等	同样用方向表加取模换向，但换向条件来自越界与重复访问
59. 螺旋矩阵 II	中等	反过来按螺旋顺序填数，重点在层边界的收缩时机
141. 环形链表	简单	同为判断是否陷入循环，但用快慢指针而非状态推导
457. 环形数组是否存在循环	中等	循环判定还要求方向一致且长度大于 1，需逐点起跳检测
796. 旋转字符串	简单	判断状态在有限次变换后能否复原，可用倍长串包含关系速判
874. 模拟行走机器人	中等	同样是转向加前进的模拟，但增加了障碍物与最远距离统计
841. 钥匙和房间	中等	判断确定性状态转移能否覆盖全部状态，靠搜索而非闭式推导
1091. 二进制矩阵中的最短路径	中等	八方向移动求最短步数，需要队列做层序扩散
LCP 17. 速算机器人	简单	指令直接作用于数值，一轮扫描即可得出闭式结果
剑指 Offer 13. 机器人的运动范围	中等	移动受数位和约束，考察可达区域的搜索与剪枝
面试题 08.02. 迷路的机器人	中等	需要输出一条具体路径，靠回溯配合失败点记忆化