LeetCode 1041. 困于环中的机器人
题目描述
题意分析
机器人从原点面朝北方出发，将同一串指令无限重复：
G前进一步，L、R分别左转、右转 90 度。判断它的全部轨迹是否始终落在某个有限范围内，不要求轨迹本身是圆形。
解法：模拟一轮指令
核心思路
[!blue]
同一串指令从不同朝向开始执行，产生的路径和净位移只会随朝向整体旋转。因此只需模拟一轮，记录净位移
(x, y)和结束方向dir，便能判断之后每轮如何变化。若一轮回到原点，后续每轮仍从原点开始，只是可能换一个方向执行同一条有限路径。朝向只有四种，所以轨迹有界。
若一轮没有回到原点，且结束仍朝北，那么每轮的净位移完全相同。执行
k轮后的位置为(k*x, k*y)，非零位移不断累积，轨迹无界。剩下的情况是一轮后朝向改变：若转了 180 度，第二轮净位移与第一轮相反，两轮抵消；若转了 90 或 270 度，连续四轮的净位移两两相反，四轮抵消。此时位置和方向都恢复初始状态，之后只会重复有限的这几轮，所以有界。
因此答案是“一轮回到原点，或者一轮后不再朝北”，两个条件满足任意一个即可。
解题步骤
- 用 0、1、2、3 分别表示北、东、南、西，初始化
(x, y) = (0, 0)、dir = 0。- 遇到
G，按dirs[dir]更新坐标；遇到L，令dir = (dir + 3) % 4；遇到R，令dir = (dir + 1) % 4。- 一轮结束后，返回
(x == 0 && y == 0) || dir != 0。
代码实现
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)$。
关键点总结
[!green]
- 比较的是整轮净位移与净旋转，不是某一步是否转过弯。
- 朝向改变时最多四轮恢复位置与方向，因此无需真的无限模拟。
易错点总结
[!yellow]
- 一轮没回原点不代表无界，朝向改变也能让后续位移抵消。
- 将两个条件取与，会把只满足其一的有界轨迹排除。
- 左转直接用方向减一取模，可能出现负下标，应加三再模四。
- 判断的是整轮结束方向，指令中出现过转弯并不等于最终朝向改变。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 874. 模拟行走机器人 | 中等 | 同样模拟位置与朝向，本题指令无限重复，可由一轮后的位移和朝向判断是否被困。 |
| 657. 机器人能否返回原点 | 简单 | 回到原点足以被困，但本题一轮不回原点而改变朝向时仍可能有界，不能只检查坐标。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！