comments	edit_url
true	https://github.com/doocs/leetcode/edit/main/lcp/LCP%2003.%20%E6%9C%BA%E5%99%A8%E4%BA%BA%E5%A4%A7%E5%86%92%E9%99%A9/README.md

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>x$ 或者 $b>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;
}