Leetcode.1041 困于环中的机器人

这篇具有很好参考价值的文章主要介绍了Leetcode.1041 困于环中的机器人。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目链接

Leetcode.1041 困于环中的机器人 Rating ： 1521

题目描述

在无限的平面上，机器人最初位于 (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 <= in s t r u c t i o n s . l e n g t h <= 100$
instructions[i]仅包含 'G', 'L', 'R'

解法：脑筋急转弯+模拟

当机器人执行完 $in s t r u c t i o n s$ 的所有指令后，它所处的位置为 $(x, y)$ ，方向为 $d i r$ 。

$\&\&y == 0$ ，当执行完指令之后，还是处于原点，说明根本就没移动。所以机器人不能离开，返回 true
$\neq 0 || y \neq 0$ ，当执行完指令之后，方向 $d i r$ 是 向南的。当 第二轮执行结束的时候，方向 $d i r$ 又会向北，并且又会回到原点 $(0, 0)$ 。所以机器人不能离开，返回 true
$\neq 0 || y \neq 0$ ，当执行完指令之后，方向 $d i r$ 是 向东的。当 第四轮执行结束的时候，方向 $d i r$ 又会向北，并且又会回到原点 $(0, 0)$ 。所以机器人不能离开，返回 true
$\neq 0 || y \neq 0$ ，当执行完指令之后，方向 $d i r$ 是 向西的。当 第四轮执行结束的时候，方向 $d i r$ 又会向北，并且又会回到原点 $(0, 0)$ 。所以机器人不能离开，返回 true
$\neq 0 || y \neq 0$ ，当执行完指令之后，方向 $d i r$ 是 向北的。那么说明机器人会一直沿着北面移动，所以最后能够离开，返回 false

时间复杂度： $O (n)$

C++代码：文章来源地址https://www.toymoban.com/news/detail-417400.html

class Solution {
public:
    bool isRobotBounded(string instructions) {
        int d[4][4] = {{0,1} , {1,0} , {0,-1} , {-1,0}};
        //初始位置
        int x = 0 , y = 0;
        //初始指向
        int dir = 0;

        for(auto c:instructions){
            if(c == 'G'){
                x += d[dir][0];
                y += d[dir][1];
            }
            else if(c == 'L'){
                dir = (dir + 3) % 4;
            }
            else if(c == 'R'){
                dir = (dir + 1) % 4;
            }
        }

        return dir != 0 || (x == 0 && y == 0);
    }
};