题目简介：
在无限的平面上，机器人最初位于 (0, 0) 处，面朝北方。注意:
- 北方向 是y轴的正方向。
- 南方向 是y轴的负方向。
- 东方向 是x轴的正方向。
- 西方向 是x轴的负方向。
机器人可以接受下列三条指令之一：
"G"：直走 1 个单位"L"：左转 90 度"R"：右转 90 度
机器人按顺序执行指令 instructions，并一直重复它们。
只有在平面中存在环使得机器人永远无法离开时，返回 true。否则，返回 false。
示例 1：
1
2
3
4
5
6
7
8
9
10
11
| 输入：instructions = "GGLLGG"
输出：true
解释：机器人最初在(0,0)处，面向北方。
“G”:移动一步。位置:(0,1)方向:北。
“G”:移动一步。位置:(0,2).方向:北。
“L”:逆时针旋转90度。位置:(0,2).方向:西。
“L”:逆时针旋转90度。位置:(0,2)方向:南。
“G”:移动一步。位置:(0,1)方向:南。
“G”:移动一步。位置:(0,0)方向:南。
重复指令，机器人进入循环:(0,0)——>(0,1)——>(0,2)——>(0,1)——>(0,0)。
在此基础上，我们返回true。
|
示例 2：
1
2
3
4
5
6
7
8
9
10
11
12
13
| 输入：instructions = "GL"
输出：true
解释：机器人最初在(0,0)处，面向北方。
“G”:移动一步。位置:(0,1)方向:北。
“L”:逆时针旋转90度。位置:(0,1).方向:西。
“G”:移动一步。位置:(- 1,1)方向:西。
“L”:逆时针旋转90度。位置:(- 1,1)方向:南。
“G”:移动一步。位置:(- 1,0)方向:南。
“L”:逆时针旋转90度。位置:(- 1,0)方向:东方。
“G”:移动一步。位置:(0,0)方向:东方。
“L”:逆时针旋转90度。位置:(0,0)方向:北。
重复指令，机器人进入循环:(0,0)——>(0,1)——>(- 1,1)——>(- 1,0)——>(0,0)。
在此基础上，我们返回true。
|
思路：
首先遍历一遍字符串，若最后的位置在原点，则说明一定循环。
否则，观察其朝向：
- 若面向北方，那么执行一遍指令的坐标变化量为
(x, y)，执行n遍为(nx, ny)，由于没有回原点，所以$nx \ne 0$或$ny \ne 0$，所以不会陷入循环。
- 若面向东方，则执行第二遍指令的坐标变化量为
(y, -x)(向量知识)，继续执行第三遍指令后，坐标变化量是(−x, −y)，继续执行第四遍指令后，坐标变化量是(−y, x)，累加四遍的变化量，可以发现回到了原点陷入循环。
- 其余两个方向类似，都会陷入循环
因此，只要最后朝向不为北，都会陷入循环。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| class Solution {
public:
bool isRobotBounded(string instructions) {
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int now_idx = 0;
int fianl_x = 0;
int fianl_y = 0;
for(auto c : instructions){
if(c == 'L'){
now_idx = (now_idx - 1 + 4) % 4;
continue;
}
else if(c == 'R'){
now_idx = (now_idx + 1) % 4;
continue;
}
fianl_x += dx[now_idx];
fianl_y += dy[now_idx];
}
if(fianl_x == 0 && fianl_y == 0 || (now_idx != 0))
return true;
return false;
}
};
|
