题目描述
力扣团队买了一个可编程机器人，机器人初始位置在原点(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的长度 <= 1000command由U，R构成，且至少有一个U，至少有一个R0 <= x <= 1e9, 0 <= y <= 1e90 <= obstacles的长度 <= 1000obstacles[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\) 的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 | 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 | 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
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 | 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;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 | class Solution {
func robot(_ command: String, _ obstacles: [[Int]], _ x: Int, _ y: Int) -> Bool {
var visited: Set<[Int]> = []
var i = 0, j = 0
visited.insert([i, j])
for c in command {
if c == "U" {
j += 1
} else {
i += 1
}
visited.insert([i, j])
}
func canReach(_ targetX: Int, _ targetY: Int) -> Bool {
let k = min(targetX / i, targetY / j)
return visited.contains([targetX - k * i, targetY - k * j])
}
if !canReach(x, y) {
return false
}
for obstacle in obstacles {
let obstacleX = obstacle[0]
let obstacleY = obstacle[1]
if obstacleX > x || obstacleY > y {
continue
}
if canReach(obstacleX, obstacleY) {
return false
}
}
return true
}
}
|