LCP 03. 机器人大冒险 

题目描述

力扣团队买了一个可编程机器人，机器人初始位置在原点(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]不为原点或者终点

解法

方法一：哈希表

我们用哈希表 $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$ 的长度。

Python3

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

Java

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;
    }
}

C++

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;
    }
};

Go

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
}

TypeScript

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;
}

Swift

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
    }
}