1041. 困于环中的机器人
题目描述
在无限大的平面上，机器人一开始位于 (0, 0)，面朝北。北是 y 轴正方向，东是 x 轴正方向。
输入指令串 instructions，只含三种字符：'G' 表示朝当前方向前进 1 格，'L' 表示原地向左转 90 度，'R' 表示原地向右转 90 度。
机器人按顺序执行整串指令，执行完后从头再来，无限重复。如果机器人的活动范围始终被限制在平面上某个有限的圈子里，返回 true；如果它会越走越远，返回 false。
示例 1
输入：instructions = "GGLLGG" 输出：true
解释：走到 (0,2) 后掉头走回 (0,0)，之后一直在这条线段上往返。
示例 2
输入：instructions = "GG" 输出：false
解释：每轮都向北多走 2 格，会无限远离原点。
示例 3
输入：instructions = "GL" 输出：true
解释：每轮左转一次，四轮后回到原点并面朝北，形成循环。
数据范围
1 <= instructions.length <= 100instructions[i]只会是'G'、'L'或'R'。
解题思路
只模拟一轮，记录位置 (x, y) 和朝向 d（0 北、1 东、2 南、3 西）。如果一轮后回到原点，显然永远在环中。如果没回到原点但朝向变了，每轮的位移会跟着朝向旋转，最多 4 轮后位移相互抵消，回到原点。只有“不在原点且仍朝北”时，每轮都朝同一方向偏移，会越走越远。
为什么正确
处理完前 i 条指令后，(x, y) 是机器人的位置，d 是它的朝向；dx[d]、dy[d] 是朝向 d 时前进一格的坐标变化。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
只判断一轮后是否回到原点是不够的："GL" 一轮后在 (0, 1)，但朝向变了，仍然会困在环中。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def isRobotBounded(self, instructions: str) -> bool:
dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
x = y = d = 0
for c in instructions:
if c == 'G':
x += dx[d]
y += dy[d]
elif c == 'L':
d = (d + 3) % 4
else:
d = (d + 1) % 4
return (x == 0 and y == 0) or d != 0class Solution {
public boolean isRobotBounded(String instructions) {
int[] dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};
int x = 0, y = 0, d = 0;
for (char c : instructions.toCharArray()) {
if (c == 'G') {
x += dx[d];
y += dy[d];
} else if (c == 'L') {
d = (d + 3) % 4;
} else {
d = (d + 1) % 4;
}
}
return (x == 0 && y == 0) || d != 0;
}
}class Solution {
public:
bool isRobotBounded(string instructions) {
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
int x = 0, y = 0, d = 0;
for (char c : instructions) {
if (c == 'G') {
x += dx[d];
y += dy[d];
} else if (c == 'L') {
d = (d + 3) % 4;
} else {
d = (d + 1) % 4;
}
}
return (x == 0 && y == 0) || d != 0;
}
};func isRobotBounded(instructions string) bool {
dx, dy := []int{0, 1, 0, -1}, []int{1, 0, -1, 0}
x, y, d := 0, 0, 0
for _, c := range instructions {
if c == 'G' {
x += dx[d]
y += dy[d]
} else if c == 'L' {
d = (d + 3) % 4
} else {
d = (d + 1) % 4
}
}
return (x == 0 && y == 0) || d != 0
}var isRobotBounded = function(instructions) {
const dx = [0, 1, 0, -1], dy = [1, 0, -1, 0];
let x = 0, y = 0, d = 0;
for (const c of instructions) {
if (c === 'G') {
x += dx[d];
y += dy[d];
} else if (c === 'L') {
d = (d + 3) % 4;
} else {
d = (d + 1) % 4;
}
}
return (x === 0 && y === 0) || d !== 0;
};function isRobotBounded(instructions: string): boolean {
const dx = [0, 1, 0, -1], dy = [1, 0, -1, 0];
let x = 0, y = 0, d = 0;
for (const c of instructions) {
if (c === 'G') {
x += dx[d];
y += dy[d];
} else if (c === 'L') {
d = (d + 3) % 4;
} else {
d = (d + 1) % 4;
}
}
return (x === 0 && y === 0) || d !== 0;
}