模拟行走机器人 II

难度: Medium

给你一个在 XY 平面上的 width x height 的网格图，左下角 的格子为 (0, 0) ，右上角 的格子为 (width - 1, height - 1) 。网格图中相邻格子为四个基本方向之一（"North"，"East"，"South" 和 "West"）。一个机器人初始在格子 (0, 0) ，方向为 "East" 。

机器人可以根据指令移动指定的步数。每一步，它可以执行以下操作。

沿着当前方向尝试 往前一步 。
如果机器人下一步将到达的格子 超出了边界 ，机器人会 逆时针 转 90 度，然后再尝试往前一步。

如果机器人完成了指令要求的移动步数，它将停止移动并等待下一个指令。

请你实现 Robot 类：

Robot(int width, int height) 初始化一个 width x height 的网格图，机器人初始在 (0, 0) ，方向朝 "East" 。
void step(int num) 给机器人下达前进 num 步的指令。
int[] getPos() 返回机器人当前所处的格子位置，用一个长度为 2 的数组 [x, y] 表示。
String getDir() 返回当前机器人的朝向，为 "North" ，"East" ，"South" 或者 "West" 。

示例 1：

example-1

输入：
["Robot", "step", "step", "getPos", "getDir", "step", "step", "step", "getPos", "getDir"]
[[6, 3], [2], [2], [], [], [2], [1], [4], [], []]
输出：
[null, null, null, [4, 0], "East", null, null, null, [1, 2], "West"]

解释：
Robot robot = new Robot(6, 3); // 初始化网格图，机器人在 (0, 0) ，朝东。
robot.step(2);  // 机器人朝东移动 2 步，到达 (2, 0) ，并朝东。
robot.step(2);  // 机器人朝东移动 2 步，到达 (4, 0) ，并朝东。
robot.getPos(); // 返回 [4, 0]
robot.getDir(); // 返回 "East"
robot.step(2);  // 朝东移动 1 步到达 (5, 0) ，并朝东。
                // 下一步继续往东移动将出界，所以逆时针转变方向朝北。
                // 然后，往北移动 1 步到达 (5, 1) ，并朝北。
robot.step(1);  // 朝北移动 1 步到达 (5, 2) ，并朝 北 （不是朝西）。
robot.step(4);  // 下一步继续往北移动将出界，所以逆时针转变方向朝西。
                // 然后，移动 4 步到 (1, 2) ，并朝西。
robot.getPos(); // 返回 [1, 2]
robot.getDir(); // 返回 "West"

提示：

2 <= width, height <= 100
1 <= num <= 10⁵
step ，getPos 和 getDir 总共调用次数不超过 10⁴ 次。

Submission

运行时间: 161 ms

内存: 20.5 MB

class Robot:

    TO_DIR = {
        0: "East",
        1: "North",
        2: "West",
        3: "South",
    }

    def __init__(self, width: int, height: int):
        self.moved = False
        self.idx = 0
        self.pos = list()
        self.dirs = list()

        pos_, dirs_ = self.pos, self.dirs

        for i in range(width):
            pos_.append((i, 0))
            dirs_.append(0)
        for i in range(1, height):
            pos_.append((width - 1, i))
            dirs_.append(1)
        for i in range(width - 2, -1, -1):
            pos_.append((i, height - 1))
            dirs_.append(2)
        for i in range(height - 2, 0, -1):
            pos_.append((0, i))
            dirs_.append(3)

        dirs_[0] = 3

    def step(self, num: int) -> None:
        self.moved = True
        self.idx = (self.idx + num) % len(self.pos)

    def getPos(self) -> List[int]:
        return list(self.pos[self.idx])

    def getDir(self) -> str:
        if not self.moved:
            return "East"
        return Robot.TO_DIR[self.dirs[self.idx]]

Explain

此题解采用了预计算的方法，通过预先存储机器人可能的所有位置和方向，以优化查询性能。在初始化时，Robot 类构建了一个沿着网格边界顺时针旋转的路径。这包括机器人从起始点开始，向东行进至最右边，然后向北至最顶部，接着向西至最左边，最后向南回到起始点上方的位置，形成一个封闭环路。此后，机器人的每一步都通过简单地索引更新来模拟，这使得移动操作非常高效。step 方法通过更新索引来模拟机器人的移动，getPos 和 getDir 方法则提供了查询当前位置和方向的功能。

时间复杂度: O(1)

空间复杂度: O(width + height)

class Robot:

    TO_DIR = {
        0: \"East\",
        1: \"North\",
        2: \"West\",
        3: \"South\",
    }

    def __init__(self, width: int, height: int):
        self.moved = False  # 标记是否有移动过
        self.idx = 0  # 当前位置索引
        self.pos = list()  # 保存所有可能的位置
        self.dirs = list()  # 保存每个位置对应的方向

        pos_, dirs_ = self.pos, self.dirs

        # 沿东边界行进
        for i in range(width):
            pos_.append((i, 0))
            dirs_.append(0)
        # 沿北边界行进
        for i in range(1, height):
            pos_.append((width - 1, i))
            dirs_.append(1)
        # 沿西边界行进
        for i in range(width - 2, -1, -1):
            pos_.append((i, height - 1))
            dirs_.append(2)
        # 沿南边界行进
        for i in range(height - 2, 0, -1):
            pos_.append((0, i))
            dirs_.append(3)

        dirs_[0] = 3  # 开始时机器人朝东，但位置（0,0）处的方向更新为南

    def step(self, num: int) -> None:
        self.moved = True  # 更新移动状态
        self.idx = (self.idx + num) % len(self.pos)  # 更新位置索引

    def getPos(self) -> List[int]:
        return list(self.pos[self.idx])  # 返回当前位置

    def getDir(self) -> str:
        if not self.moved:
            return \"East\"  # 默认起始方向为东
        return Robot.TO_DIR[self.dirs[self.idx]]  # 返回当前方向

Explore

在初始化时预先计算并存储所有可能的位置和方向可以大大提高每次调用step方法的效率。如果每次调用step时都动态计算位置和方向，那么每次操作都需要重新计算机器人的路径，这在机器人进行大量移动时将非常耗时。使用预计算的方式，机器人的移动可以通过简单的索引更新来实现，这使得每次移动的时间复杂度为常数O(1)，从而优化了性能。

在沿南边界移动时，位置从(height - 2, 0)开始向(0, 0)递减是因为机器人已经在西边界的最下方(height - 1, 0)，因此接下来需要回到起始点的上方(0, 0)。递减的步长是1，即每次移动将纵坐标减1。这种设计确保了机器人不会错过(0, 0)位置，因为最后一个位置正好是(0, 0)上方的(0, 1)。

这里的设置确实有误。根据题目描述，机器人应该是初始朝向东方。因此dirs_[0]应该被设置为0（'East'），而不是3（'South'）。这个错误可能是代码编写时的疏忽。正确设置应确保机器人的初始方向与题目描述一致。

如果按照代码中的设计，确实会存在这样的问题。因为初始方向在dirs_数组中被设置为'East'，所以即使机器人的实际初始方向应该是其他方向，只要它未移动过，getDir方法仍然会返回'East'。这种设计在未移动时不考虑实际的初始方向，因此在不符合题目描述的初始设置下会导致错误的方向输出。这要求在实现时正确设置初始方向，并在getDir方法中根据是否移动过返回正确的方向。