当前位置：首页 > article >正文

LeetCode 1041. 困于环中的机器人

article 2024/9/19 7:20:12

【LetMeFly】1041.困于环中的机器人

力扣题目链接：https://leetcode.cn/problems/robot-bounded-in-circle/

在无限的平面上，机器人最初位于 (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，结束状态为什么的时候说明会被困住（多次执行会循环）

当执行结束时，恰好回到了起点或者当前方向不为北的话，多次执行必定会回到起点。

首先如果执行一次回到了起点，那么之后执行也会回到起点，顶多每次的方向不同；

其次如果结束时方向不为北的话，4次或2次内就会绕回到起点。例如：GL等。

具体方法

知道了解题思路，怎么编程实现模拟呢？

首先我们可以定义一个数组，代表朝向为北东南西时，前进一步的坐标变化。directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]

接着使用一个变量记录当前方向，向右转时方向加一并对4取模，向左转时方向加三并对4取模（相当于方向减一后取模），向前走时就坐标累加即可。

（当然，无脑模拟4次判断是否回到了起点也可以）

时间复杂度 $O (l e n (in s t r u c t i o n s))$
空间复杂度 $O (1)$

AC代码

C++

const int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};  // 北东南西

class Solution {
public:
    bool isRobotBounded(string& instructions) {
        int nowDirection = 0;
        int x = 0, y = 0;
        for (char c : instructions) {
            if (c == 'G') {
                x += directions[nowDirection][0];
                y += directions[nowDirection][1];
            }
            else if (c == 'L') {
                nowDirection = (nowDirection + 3) % 4;
            }
            else {
                nowDirection = (nowDirection + 1) % 4;
            }
        }
        return nowDirection || (!x && !y);
    }
};

Python

directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]

class Solution:
    def isRobotBounded(self, instructions: str) -> bool:
        nowDirection = 0
        x, y = 0, 0
        for c in instructions:
            if c == 'G':
                x += directions[nowDirection][0]
                y += directions[nowDirection][1]
            elif c == 'L':
                nowDirection = (nowDirection + 3) % 4
            else:
                nowDirection = (nowDirection + 1) % 4
        return nowDirection != 0 or (not x and not y)