困于环中的机器人Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

在无限的平面上，机器人最初位于 (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 <= 100
instructions[i] 仅包含 'G', 'L', 'R'

# 思路

// instructions可以简化为一个向量跟最终面朝方向。

// 如果最终面朝方向与原始面朝方向垂直，那么机器人走四次instructions会回到原点形成闭环。（四个向量组成一个正方形） // 如果最终面朝方向是原始面朝方向的反方向，则下一次instructions必定会到原点。（两个方向相反的向量） // 如果面朝方向不变，向量不是零则发散，是零则一直在原点。

# 解法


class Solution {
// instructions可以简化为一个向量跟最终面朝方向。

// 如果最终面朝方向与原始面朝方向垂直，那么机器人走四次instructions会回到原点形成闭环。（四个向量组成一个正方形）
// 如果最终面朝方向是原始面朝方向的反方向，则下一次instructions必定会到原点。（两个方向相反的向量）
// 如果面朝方向不变，向量不是零则发散，是零则一直在原点。
    int[][] vecs = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    public boolean isRobotBounded(String instructions) {
        int x = 0, y = 0, dir = 0;
        for (char c : instructions.toCharArray()) {
            if (c == 'G') {
                x += vecs[dir][0];
                y += vecs[dir][1];
            } else if (c == 'L') {
                dir = (dir + 3) % 4;
            } else {
                dir = (dir + 1) % 4;
            }
        }
        if (dir == 0) return x == 0 && y == 0;
        return true;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 总结

分析出几种情况，然后分别对各个情况实现