LC 1041. 困于环中的机器人

题目描述

这是 LeetCode 上的 1041. 困于环中的机器人 ，难度为 中等。

在无限的平面上，机器人最初位于 $(0, 0)$ 处，面朝北方。注意:

  • 北方向 是 y 轴的正方向。
  • 南方向 是 y 轴的负方向。
  • 东方向 是 x 轴的正方向。
  • 西方向 是 x 轴的负方向。

机器人可以接受下列三条指令之一：

  • "G"：直走 $1$ 个单位
  • "L"：左转 $90$ 度
  • "R"：右转 $90$ 度

机器人按顺序执行指令 instructions，并一直重复它们。

只有在平面中存在环使得机器人永远无法离开时，返回 true。否则，返回 false。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
13
输入：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：
1
2
3
4
5
6
7
8
9
输入：instructions = "GG"

输出：false

解释：机器人最初在(0,0)处，面向北方。
“G”:移动一步。位置:(0,1)方向:北。
“G”:移动一步。位置:(0,2).方向:北。
重复这些指示，继续朝北前进，不会进入循环。
在此基础上，返回false。

示例 3：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入：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 记为 s，“北西南东”四个方向分别记为“上左下右”四个逆时针方向。

起始位置在 $(0,0)$，方向为上，我们可以将「位置 + 方向」统称为「状态」。

所谓“循环”，则是指执行若干次的 s 后，会回到相同的状态。

我们可以按 s 执行一遍，假设执行完所在位置为 $(x, y)$，所在位置为 $k$，先根据 位置 分情况讨论：

  1. $(x, y)$ 为 $(0, 0)$，此时无论执行一遍后的方向为何值，必然能在若干次执行后回到起始状态。

    即只需要确保 (n * k) % 4 为 $0$ 即可，机器人会陷入循环；

  2. $(x, y)$ 不为 $(0, 0)$，再根据 方向 进一步分情况讨论：

    • 方向为上：每执行一遍 s 指令，位置变化为 $(x, y)$，方向不变。

      那么执行 $n$ 遍后位置为 $(n \times x, n \times y)$，其中 $n$ 为正整数，并且 $x$ 和 $y$ 不同时为 $0$，因此随着执行次数增加，位置会离 $(0, 0)$ 越来越远，机器人不会陷入循环；

    • 方向为下：每执行一遍 s 指令，位置变化为 $(x, y)$，方向翻转。

      如果再执行一遍，由于再次执行时的方向与起始方向相反，因此位置变化为 $(-x, -y)$，同时方向再次翻转（与起始方向一致）。即执行偶数次后，会回到起始状态，机器人会陷入循环；

    • 方向为左：每执行一遍 s 指令，位置变化为 $(x, y)$，方向为逆时针 $90$ 度。

      如果执行第二次，位置变化为 $(-y, x)$，方向再逆时针 $90$ 度（与起始方向相反）；执行第三次，位置变化为 $(-x, -y)$，方向再逆时针 $90$ 度（与起始方向呈顺时针 $90$ 度），该次变化会和首次执行相互抵消；执行第四次，位置变化为 $(y, -x)$，方向再逆时针 $90$ 度（与起始方向相同），该次变化与第二次执行相互抵消。总的位置变化为 $(0, 0)$，同时方向与起始方向一致，机器人会陷入循环；

    • 方向为右：与「方向为左」同理，机器人会陷入循环。

综上，只要执行一遍 s 后所在位置为 $(0, 0)$ 或方向不为上，均可确保循环发生。

Java 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean isRobotBounded(String s) {
        int x = 0, y = 0, d = 0;
        int[][] dirs = new int[][]{{0,1}, {-1,0}, {0,-1}, {1,0}};
        for (char c : s.toCharArray()) {
            if (c == 'G') {
                x += dirs[d][0]; y += dirs[d][1];
            } else if (c == 'L') {
                d = (d + 1) % 4;
            } else {
                d = ((d - 1) % 4 + 4) % 4;
            }
        }
        return (x == 0 && y == 0) || d != 0;
    }
}

C++ 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool isRobotBounded(string s) {
        int x = 0, y = 0, d = 0;
        int dirs[4][2] = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};
        for (char c : s) {
            if (c == 'G') {
                x += dirs[d][0]; y += dirs[d][1];
            } else if (c == 'L') {
                d = (d + 1) % 4;
            } else {
                d = ((d - 1) % 4 + 4) % 4;
            }
        }
        return (x == 0 && y == 0) || d != 0;
    }
};

Python 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def isRobotBounded(self, s: str) -> bool:
        x, y, d = 0, 0, 0
        dirs = [[0, 1], [-1, 0], [0, -1], [1, 0]]
        for c in s:
            if c == 'G':
                x += dirs[d][0]
                y += dirs[d][1]
            elif c == 'L':
                d = (d + 1) % 4
            else:
                d = ((d - 1) % 4 + 4) % 4
        return (x == 0 and y == 0) or d != 0

Go 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func isRobotBounded(s string) bool {
    x, y, d := 0, 0, 0
    dirs := [][]int{{0, 1}, {-1, 0}, {0, -1}, {1, 0}}
    for _, c := range s {
        if c == 'G' {
            x += dirs[d][0]
            y += dirs[d][1]
        } else if c == 'L' {
            d = (d + 1) % 4
        } else {
            d = ((d - 1) % 4 + 4) % 4
        }
    }
    return (x == 0 && y == 0) || d != 0
}

TypeScript 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function isRobotBounded(s: string): boolean {
    let x = 0, y = 0, d = 0;
    const dirs: number[][] = [[0, 1], [-1, 0], [0, -1], [1, 0]];
    for (const c of s) {
        if (c === 'G') {
            x += dirs[d][0];
            y += dirs[d][1];
        } else if (c === 'L') {
            d = (d + 1) % 4;
        } else {
            d = ((d - 1) % 4 + 4) % 4;
        }
    }
    return (x === 0 && y === 0) || d !== 0;
};

  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1041 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

模拟 脑筋急转弯

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！