机器人大冒险

难度: Medium

力扣团队买了一个可编程机器人，机器人初始位置在原点(0, 0)。小伙伴事先给机器人输入一串指令command，机器人就会无限循环这条指令的步骤进行移动。指令有两种：

U: 向y轴正方向移动一格
R: 向x轴正方向移动一格。

不幸的是，在 xy 平面上还有一些障碍物，他们的坐标用obstacles表示。机器人一旦碰到障碍物就会被损毁。

给定终点坐标(x, y)，返回机器人能否完好地到达终点。如果能，返回true；否则返回false。

示例 1：

输入：command = "URR", obstacles = [], x = 3, y = 2
输出：true
解释：U(0, 1) -> R(1, 1) -> R(2, 1) -> U(2, 2) -> R(3, 2)。

示例 2：

输入：command = "URR", obstacles = [[2, 2]], x = 3, y = 2
输出：false
解释：机器人在到达终点前会碰到(2, 2)的障碍物。

示例 3：

输入：command = "URR", obstacles = [[4, 2]], x = 3, y = 2
输出：true
解释：到达终点后，再碰到障碍物也不影响返回结果。

限制：

2 <= command的长度 <= 1000
command由U，R构成，且至少有一个U，至少有一个R
0 <= x <= 1e9, 0 <= y <= 1e9
0 <= obstacles的长度 <= 1000
obstacles[i]不为原点或者终点

Submission

运行时间: 31 ms

内存: 16.5 MB

class Solution:
    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:

        xi = 0
        yi = 0

        # 计算第一次执行完command后, 走过的所有坐标
        first_coor = [[0, 0]]
        for c in command:
            if c == 'R' :
                xi += 1
            else:
                yi += 1
            first_coor.append([xi, yi])
        
        # 此时(xi, yi)也代表着初次command执行结束时走到的最后一个坐标
        # 走到目标点所需要的循环次数
        circle = min(x // xi, y // yi)

        if [x - xi * circle, y - yi * circle] not in first_coor:
            return False

        # 对每个阻碍点逐个判断，是否会走到它
        for obstacle in obstacles:
            ob_x, ob_y = obstacle[0], obstacle[1]
            # 走到阻碍点所需要的循环数（若是能走到的话）
            circle = min(ob_x // xi, ob_y // yi)
            # 判断是否会走到这个阻碍点，注意在终点之后的阻碍点可以忽略
            if ob_x <= x and ob_y <= y and [ob_x - xi * circle, ob_y - yi * circle] in first_coor:
                return False 

        return True

Explain

该题解采用的是模拟机器人行走的方式。首先，根据输入的command，模拟机器人第一次执行完这串指令后经过的所有坐标点，并存储起来。接着，利用目标点和障碍点的坐标，计算机器人在到达这些点前需要循环执行指令的次数，以判断是否能够到达目标点，以及是否会碰到障碍物。如果机器人在到达目标点之前碰到任何障碍物，则返回False；如果能够安全到达目标点，则返回True。

时间复杂度: O(n + m)

空间复杂度: O(n)

class Solution:
    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:

        xi = 0
        yi = 0

        # 计算第一次执行完command后, 走过的所有坐标
        first_coor = [[0, 0]]
        for c in command:
            if c == 'R' :
                xi += 1
            else:
                yi += 1
            first_coor.append([xi, yi])
        
        # 此时(xi, yi)也代表着初次command执行结束时走到的最后一个坐标
        # 走到目标点所需要的循环次数
        circle = min(x // xi, y // yi)

        if [x - xi * circle, y - yi * circle] not in first_coor:
            return False

        # 对每个阻碍点逐个判断，是否会走到它
        for obstacle in obstacles:
            ob_x, ob_y = obstacle[0], obstacle[1]
            # 走到阻碍点所需要的循环数（若是能走到的话）
            circle = min(ob_x // xi, ob_y // yi)
            # 判断是否会走到这个阻碍点，注意在终点之后的阻碍点可以忽略
            if ob_x <= x and ob_y <= y and [ob_x - xi * circle, ob_y - yi * circle] in first_coor:
                return False 

        return True

Explore

在题解的算法中，假设command中至少含有一个'R'和一个'U'，因此xi和yi在执行完一次command后不会为0。然而，如果command中仅包含'R'或'U'，那么xi或yi可能为0。在实际实现中，应当在代码中检查xi和yi是否为0，如果是，则需要特殊处理或者返回错误信息。例如，如果xi为0（即command中没有'R'），只有当目标点x坐标也为0时，机器人才可能到达目标点或考虑障碍物，否则直接返回False。同理，如果yi为0，处理方法也相同。

确实，如果command非常长，存储每个经过的坐标点会消耗大量内存。这种问题可以通过优化数据结构来减少内存使用。例如，可以使用哈希集合（HashSet）来存储坐标，而不是列表（List）。这样可以提高检查坐标是否存在的效率，同时相比列表，哈希集合可以减少一些内存占用。另外，考虑到机器人路径的周期性，可以只存储一个周期内的坐标点，而不是整个command执行过程中的所有坐标。

使用 min(x // xi, y // yi) 来计算循环次数是基于假设机器人沿着最初的路径直线前进，并在每个周期结束时检查其位置是否达到或超过目标点。这种方法能够有效地计算到达目标点的最小循环次数，但对于障碍物的检查可能不够准确，因为障碍物可能出现在路径的任何位置。因此，对于每个障碍物，都需要独立计算其所需的循环次数，并检查在该循环次数下，机器人是否会经过障碍物的坐标。如果任一障碍物位于机器人到达目标点之前的路径上，则返回False。这种方法确保了在到达目标点之前，任何障碍物都会被考虑进去。