[LeetCode] 1041. Robot Bounded In Circle

[grandyang]

On an infinite plane, a robot initially stands at (0, 0) and faces north. The robot can receive one of three instructions:

• "G": go straight 1 unit;
• "L": turn 90 degrees to the left;
• "R": turn 90 degrees to the right.

The robot performs the instructions given in order, and repeats them forever.

Return true if and only if there exists a circle in the plane such that the robot never leaves the circle.

Example 1:

Input: instructions = "GGLLGG"
Output: true
Explanation: The robot moves from (0,0) to (0,2), turns 180 degrees, and then returns to (0,0).
When repeating these instructions, the robot remains in the circle of radius 2 centered at the origin.

Example 2:

Input: instructions = "GG"
Output: false
Explanation: The robot moves north indefinitely.

Example 3:

Input: instructions = "GL"
Output: true
Explanation: The robot moves from (0, 0) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (0, 0) -> ...

Constraints:

• 1 <= instructions.length <= 100
• instructions[i] is 'G', 'L' or, 'R'.

这道题说是在一个无限大的区域，有个机器人初始化站在原点 (0, 0) 的位置，面朝北方。该机器人有三种指令可以执行，G表示朝当前方向前进一步，L表示向左转 90 度，R表示向右转 90 度，现在给了一些连续的这样的指令，若一直重复的按顺序循环执行下去，问机器人是否会在一个固定的圆圈路径中循环。首先我们需要执行一遍所有的指令，然后根据最后的状态（包括位置和朝向）来分析机器人是否之后会一直走循环路线。若执行过一遍所有指令之后机器人还在原点上，则一定是在一个圆圈路径上（即便是机器人可能就没移动过，一个点也可以看作是圆圈路径）。若机器人偏离了起始位置，只要看此时机器人的朝向，只要不是向北，则其最终一定会回到起点，别问博主怎么证明，博主也不知道，大家可以多带几个例子试一下。知道了最终状态和循环路径的关系，现在就是如何执行这些指令了。也不难，用一个变量表示当前的方向，0表示北，1为东，2为南，3为西，按这个顺序写出偏移量数组 dirs，就是在迷宫遍历的时候经常用到的那个数组。然后记录当前位置 cur，初始化为 (0, 0)，然后就可以执行指令了，若遇到G指令，根据 idx 从 dirs 数组中取出偏移量加到 cur 上即可。若遇到L指令，idx 是要减1的，为了避免负数，先加上个4，再减1，再对4取余。同理，若遇到R指令，idx 加1之后对4取余。最后判断若还在原点，或者朝向不为北的时候，返回 true 即可，参见代码如下：

class Solution {
public:
    bool isRobotBounded(string instructions) {
        int idx = 0; // 0 north, 1 east, 2 south, 3 west.
        vector<int> cur{0, 0};
        vector<vector<int>> dirs{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        for (char c : instructions) {
            if (c == 'G') {
                cur = {cur[0] + dirs[idx][0], cur[1] + dirs[idx][1]};
            } else if (c == 'L') {
                idx = (idx + 4 - 1) % 4;
            } else {
                idx = (idx + 1) % 4;
            }
        }
        return (cur[0] == 0 && cur[1] == 0) || idx > 0;
    }
};

Github 同步地址:

#1041

参考资料：

https://leetcode.com/problems/robot-bounded-in-circle/

https://leetcode.com/problems/robot-bounded-in-circle/discuss/290856/JavaC%2B%2BPython-Let-Chopper-Help-Explain

LeetCode All in One 题目讲解汇总(持续更新中...)