1041. Robot Bounded In Circle

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 同步地址:

https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation