1041-困于环中的机器人

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 17:01:07 2023-09-13 17:01:07 Updated    

在无限的平面上，机器人最初位于 (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 后，它的位置和方向均有可能发生变化。

  • 如果它的位置仍位于原点，那么不管它此时方向是什么，机器人都将永远无法离开。

  • 如果它的位置不在原点，那么需要考虑此时机器人的方向：

    • 如果机器人仍然朝北，那么机器人可以不会陷入循环。假设执行完一串指令后，机器人的位置是 (x, y) 且不为原点，方向仍然朝北，那么执行完第二串指令后，机器人的位置便成为 (2\times x, 2\times y)，会不停地往外部移动，不会陷入循环。
    • 如果机器人朝南，那么执行第二串指令时，机器人的位移会与第一次相反，即第二次的位移是 (-x, -y)，并且结束后会回到原来的方向。这样一来，每两串指令之后，机器人都会回到原点，并且方向朝北，机器人会陷入循环。
    • 如果机器人朝东，即右转了 90\degree。这样一来，每执行一串指令，机器人都会右转 90\degree。那么第一次和第三次指令的方向是相反的，第二次和第四次指令的方向是相反的，位移之和也为 0，这样一来，每四次指令之后，机器人都会回到原点，并且方向朝北，机器人会陷入循环。如果机器人朝西，也是一样的结果。

因此，机器人想要摆脱循环，在一串指令之后的状态，必须是不位于原点且方向朝北。

代码

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def isRobotBounded(self, instructions: str) -> bool:
        direc = [[0, 1], [1, 0], [0, -1], [-1, 0]]
        direcIndex = 0
        x, y = 0, 0
        for instruction in instructions:
            if instruction == 'G':
                x += direc[direcIndex][0]
                y += direc[direcIndex][1]
            elif instruction == 'L':
                direcIndex -= 1
                direcIndex %= 4
            else:
                direcIndex += 1
                direcIndex %= 4
        return direcIndex != 0 or (x == 0 and y == 0)
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean isRobotBounded(String instructions) {
        int[][] direc = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
        int direcIndex = 0;
        int x = 0, y = 0;
        int n = instructions.length();
        for (int idx = 0; idx < n; idx++) {
            char instruction = instructions.charAt(idx);
            if (instruction == 'G') {
                x += direc[direcIndex][0];
                y += direc[direcIndex][1];
            } else if (instruction == 'L') {
                direcIndex += 3;
                direcIndex %= 4;
            } else {
                direcIndex++;
                direcIndex %= 4;
            }
        }
        return direcIndex != 0 || (x == 0 && y == 0);
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool isRobotBounded(string instructions) {
        vector<vector<int>> direc { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
        int direcIndex = 0;
        int x = 0, y = 0;
        for (char instruction : instructions) {
            if (instruction == 'G') {
                x += direc[direcIndex][0];
                y += direc[direcIndex][1];
            } else if (instruction == 'L') {
                direcIndex += 3;
                direcIndex %= 4;
            } else {
                direcIndex++;
                direcIndex %= 4;
            }
        }
        return direcIndex != 0 || (x == 0 && y == 0);
    }
};
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func isRobotBounded(instructions string) bool {
    direc := [][]int{ {0, 1}, {1, 0}, {0, -1}, {-1, 0} }
    direcIndex := 0
    x, y := 0, 0
    n := len(instructions)
    for i := 0; i < n; i++ {
        instruction := instructions[i]
        if instruction == 'G' {
            x += direc[direcIndex][0]
            y += direc[direcIndex][1]
        } else if instruction == 'L' {
            direcIndex += 3
            direcIndex %= 4
        } else {
            direcIndex++
            direcIndex %= 4
        }
    }
    return direcIndex != 0 || (x == 0 && y == 0)
}

[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var isRobotBounded = function(instructions) {
    const direc = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    let direcIndex = 0
    let x = 0, y = 0
    const n = instructions.length
    for (let i = 0; i < n; i++) {
        let instruction = instructions[i]
        if (instruction === 'G') {
            x += direc[direcIndex][0]
            y += direc[direcIndex][1]
        } else if (instruction === 'L') {
            direcIndex += 3
            direcIndex %= 4
        } else {
            direcIndex++
            direcIndex %= 4
        }
    }
    return direcIndex !== 0 || (x === 0 && y === 0)
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public bool IsRobotBounded(string instructions) {
        int[][] direc = {new int[]{0, 1}, new int[]{1, 0}, new int[]{0, -1}, new int[]{-1, 0} };
        int direcIndex = 0;
        int x = 0, y = 0;
        int n = instructions.Length;
        for (int idx = 0; idx < n; idx++) {
            char instruction = instructions[idx];
            if (instruction == 'G') {
                x += direc[direcIndex][0];
                y += direc[direcIndex][1];
            } else if (instruction == 'L') {
                direcIndex += 3;
                direcIndex %= 4;
            } else {
                direcIndex++;
                direcIndex %= 4;
            }
        }
        return direcIndex != 0 || (x == 0 && y == 0);
    }
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool isRobotBounded(char * instructions) {
    int direc[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
    int direcIndex = 0;
    int x = 0, y = 0;
    int n = strlen(instructions);
    for (int i = 0; i < n; i++) {
        char instruction = instructions[i];
        if (instruction == 'G') {
            x += direc[direcIndex][0];
            y += direc[direcIndex][1];
        } else if (instruction == 'L') {
            direcIndex += 3;
            direcIndex %= 4;
        } else {
            direcIndex++;
            direcIndex %= 4;
        }
    }
    return direcIndex != 0 || (x == 0 && y == 0);
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是 instructions 的长度，需要遍历 instructions 一次。

  • 空间复杂度：O(1)，只用到常数空间。

 Comments
On this page
1041-困于环中的机器人