在无限的平面上，机器人最初位于 (0, 0) 处，面朝北方。注意:
- 北方向 是y轴的正方向。
- 南方向 是y轴的负方向。
- 东方向 是x轴的正方向。
- 西方向 是x轴的负方向。
机器人可以接受下列三条指令之一：
"G"：直走 1 个单位"L"：左转 90 度"R"：右转 90 度
机器人按顺序执行指令 instructions，并一直重复它们。
只有在平面中存在环使得机器人永远无法离开时，返回 true。否则，返回 false。
示例 1：
输入：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：
输入：instructions = "GG" 输出：false 解释：机器人最初在(0,0)处，面向北方。 “G”:移动一步。位置:(0,1)方向:北。 “G”:移动一步。位置:(0,2).方向:北。 重复这些指示，继续朝北前进，不会进入循环。 在此基础上，返回false。
示例 3：
输入：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。
提示：
1 <= instructions.length <= 100instructions[i]仅包含'G', 'L', 'R'
我最开始思考的是要不要用 set（大脑短路……）于是脑淤血代码如下：
class Solution {
public:
struct P{
int x;
int y;
};
bool isRobotBounded(string instructions) {
int dire=0;
P pl = {0,0};
set<P> s;
for(int i=0;i<instructions.size();i++){
if(instructions[i] == 'L'){
dire++;dire = dire % 4;
}
if(instructions[i] == 'R'){
dire--;
if(dire<0)dire += 4;
}
if(instructions[i] == 'G'){
if(dire == 0)pl.y++;
if(dire == 1)pl.x++;
if(dire == 2)pl.y--;
if(dire == 3)pl.x--;
}
if(s.find(pl) != s.end())s.insert(pl);
else return true;
}
return false;
}
};这玩意儿肯定过不了编译的啊，后来思考了一下只需跟踪终点坐标和方向即可，时空复杂度均达到最优（后来看了一下，还是没读明白题，我以为的是只要有环就返回 true，实际上应该是有(0,0)的环才返回true……）
代码如下：
#include <string>
class Solution {
public:
bool isRobotBounded(std::string instructions) {
// 方向向量：0: 北, 1: 东, 2: 南, 3: 西
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int x = 0, y = 0;
int dir = 0; // 初始朝北
for (char c : instructions) {
if (c == 'G') {
x += dx[dir];
y += dy[dir];
} else if (c == 'L') {
dir = (dir + 3) % 4; // 向左转 90 度
} else if (c == 'R') {
dir = (dir + 1) % 4; // 向右转 90 度
}
}
// 满足条件：回到原点 或 方向改变
return (x == 0 && y == 0) || (dir != 0);
}
};
文章评论