力扣---1041. 困于环中的机器人

发布时间 2023-04-11 17:12:23作者: Owlwu

在无限的平面上,机器人最初位于 (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'

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/robot-bounded-in-circle
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


 

基础模拟即可,可以预见的是,如果在四轮内任意一轮,机器人都不会处于(0,0)点,那么必定可以离开。

由于四轮的每次移动都是固定的,那么移动一轮后,可以直接预测出接下来的路径。

1. 如果一轮后,方向仍然为北方,那么不管经历多少轮,结束后都只会面向北方。此时只需要判定第一轮结束后的位置是否是(0,0)即可。

2. 如果一轮后,方向为西方,那么第二轮结束是南方,第三轮东方,第四轮北方。可以想到,第一轮和第三轮的方向和距离是相反的,第二轮和第四轮的方向和距离是相反的,此时一定会回到原点且面向北方。

3. 方向为东方和 2. 同理。

4. 方向为南方,由 2. 的思路,此时每过两轮,机器人都会回到原点且面向北方。

代码如下:

class Solution {
    public boolean isRobotBounded (String instructions) {
        // 0:北方,1:西方,2:南方,3:东方。
        // L:direction --, R:direction ++
        int direction = 0;
        int x = 0;
        int y = 0;
        for (int j = 0; j < instructions.length(); j++) {
            char c = instructions.charAt(j);
            if (c == 'G') {
                if (direction == 0) {
                    y++;
                } else if (direction == 1) {
                    x--;
                } else if (direction == 2) {
                    y--;
                } else {
                    x++;
                }
            } else if (c == 'L') {
                if (direction == 3) {
                    direction = 0;
                } else {
                    direction++;
                }
            } else {
                if (direction == 0) {
                    direction = 3;
                } else {
                    direction--;
                }
            }
        }
        return direction != 0 || (x == 0 && y == 0);
    }
}