Question

LCP 03. 机器人大冒险

题目描述

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

1. U : 向 y 轴正方向移动一格
2. 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
解释：到达终点后，再碰到障碍物也不影响返回结果。

限制：

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

解法

方法一：哈希表

我们用哈希表 $vis$ 记录机器人在一轮指令执行完毕后所能到达的所有位置。初始时，机器人位于原点 $(0, 0)$，因此 $vis$ 中只包含一个元素 $(0, 0)$。随后我们遍历指令 $command$ 中的每个字符 $c$，更新机器人的位置，加入哈希表 $vis$ 中。记第一轮执行完毕后，机器人所在的位置为 $(i, j)$。

如果机器人重复执行多轮指令，那么实际上机器人的位置是在 $vis$ 中的所有位置的线性组合。我们将 $(x, y)$ 分别减去 $k$ 倍 $(i, j)$ 的偏移量，其中 $k = \min(\lfloor x / i \rfloor, \lfloor y / j \rfloor)$，如果 $(x, y)$ 不在 $vis$ 中， 说明机器人不可能到达 $(x, y)$，返回 false 。

接下来，我们只需要判断机器人有没有经过障碍点即可。

我们遍历所有障碍点 $(a, b)$，如果 $a \gt x$ 或者 $b \gt y$，说明机器人不会经过该障碍点，跳过即可。否则，我们将 $(x, y)$ 分别减去 $k$ 倍 $(i, j)$ 的偏移量，其中 $k = \min(\lfloor a / i \rfloor, \lfloor b / j \rfloor)$，如果 $(a, b)$ 在 $vis$ 中，说明机器人会经过该障碍点，返回 false 。

否则，遍历结束后，返回 true 。

时间复杂度 $O(m + n)$，空间复杂度 $O(m)$。其中 $m$ 和 $n$ 分别是指令 $command$ 和障碍数组 $obstacles$ 的长度。

class Solution:
  def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:
    vis = {(0, 0)}
    i = j = 0
    for c in command:
      match c:
        case "U":
          j += 1
        case "R":
          i += 1
      vis.add((i, j))
    k = min(x // i, y // j)
    if (x - k * i, y - k * j) not in vis:
      return False
    for a, b in obstacles:
      if a > x or b > y:
        continue
      k = min(a // i, b // j)
      if (a - k * i, b - k * j) in vis:
        return False
    return True

class Solution {
  public boolean robot(String command, int[][] obstacles, int x, int y) {
    Set<List<Integer>> vis = new HashSet<>();
    int i = 0, j = 0;
    vis.add(List.of(i, j));
    for (char c : command.toCharArray()) {
      if (c == 'U') {
        ++j;
      } else {
        ++i;
      }
      vis.add(List.of(i, j));
    }
    int k = Math.min(x / i, y / j);
    if (!vis.contains(List.of(x - k * i, y - k * j))) {
      return false;
    }
    for (int[] ob : obstacles) {
      if (ob[0] > x || ob[1] > y) {
        continue;
      }
      k = Math.min(ob[0] / i, ob[1] / j);
      if (vis.contains(List.of(ob[0] - k * i, ob[1] - k * j))) {
        return false;
      }
    }
    return true;
  }
}

class Solution {
public:
  bool robot(string command, vector<vector<int>>& obstacles, int x, int y) {
    set<pair<int, int>> vis;
    int i = 0, j = 0;
    vis.insert({i, j});
    for (char c : command) {
      if (c == 'U') {
        ++j;
      } else {
        ++i;
      }
      vis.insert({i, j});
    }
    int k = min(x / i, y / j);
    if (!vis.count({x - k * i, y - k * j})) {
      return false;
    }
    for (auto& ob : obstacles) {
      if (ob[0] > x || ob[1] > y) {
        continue;
      }
      k = min(ob[0] / i, ob[1] / j);
      if (vis.count({ob[0] - k * i, ob[1] - k * j})) {
        return false;
      }
    }
    return true;
  }
};

func robot(command string, obstacles [][]int, x int, y int) bool {
  type pair struct{ i, j int }
  vis := map[pair]bool{}
  i, j := 0, 0
  vis[pair{0, 0}] = true
  for _, c := range command {
    if c == 'U' {
      j++
    } else {
      i++
    }
    vis[pair{i, j}] = true
  }
  k := min(x/i, y/j)
  if !vis[pair{x - k*i, y - k*j}] {
    return false
  }
  for _, ob := range obstacles {
    if ob[0] > x || ob[1] > y {
      continue
    }
    k := min(ob[0]/i, ob[1]/j)
    if vis[pair{ob[0] - k*i, ob[1] - k*j}] {
      return false
    }
  }
  return true
}

function robot(command: string, obstacles: number[][], x: number, y: number): boolean {
  const f = (i: number, j: number): number => {
    return i * (10 ** 9 + 1) + j;
  };
  const vis: Set<number> = new Set();
  vis.add(f(0, 0));
  let [i, j] = [0, 0];
  for (const c of command) {
    if (c === 'U') {
      ++j;
    } else {
      ++i;
    }
    vis.add(f(i, j));
  }
  const k = Math.min(Math.floor(x / i), Math.floor(y / j));
  if (!vis.has(f(x - k * i, y - k * j))) {
    return false;
  }
  for (const [a, b] of obstacles) {
    if (a > x || b > y) {
      continue;
    }
    const k = Math.min(Math.floor(a / i), Math.floor(b / j));
    if (vis.has(f(a - k * i, b - k * j))) {
      return false;
    }
  }
  return true;
}