class Solution {
public:
bool robot(string command, vector<vector<int>>& obstacles, int x, int y) {
}
};
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的长度 <= 1000command由U，R构成，且至少有一个U，至少有一个R0 <= x <= 1e9, 0 <= y <= 1e90 <= obstacles的长度 <= 1000obstacles[i]不为原点或者终点原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 2.3 MB, 提交时间: 2023-06-29 09:38:42
// 1：先判断某点需要几步：m = x + y
// 2：判断m步中有多少个R和U,如果R的数量等于x并且,U的数量等于y，则该点在路径上；否则不在路径上
func robot(command string, obstacles [][]int, x int, y int) bool {
// 如果目标点不在路径上，返回失败
if !isOnThePath(command, x, y) {
return false
}
for _, o := range obstacles {
// 判断有效的故障点是否在路径上（故障的步数大于等于目标的点，视为无效故障）
if (x+y > o[0]+o[1]) && isOnThePath(command, o[0], o[1]) {
return false
}
}
return true
}
func isOnThePath(command string, x int, y int) bool {
uNum := strings.Count(command, "U")*((x+y)/len(command)) + strings.Count(command[0:(x+y)%len(command)], "U")
rNum := strings.Count(command, "R")*((x+y)/len(command)) + strings.Count(command[0:(x+y)%len(command)], "R")
if uNum == y && rNum == x {
return true
}
return false
}
cpp 解法, 执行用时: 12 ms, 内存消耗: 7.9 MB, 提交时间: 2023-06-29 09:36:12
class Solution {
public:
bool robot(string command, vector<vector<int>>& obstacles, int x, int y) {
unordered_set<long> s;
int xx = 0,yy = 0;
s.insert(0);
for(auto c : command){
if(c == 'U') yy++;
else if(c == 'R')xx++;
s.insert(((long)xx << 30) | yy);
}
int circle = min(x/xx,y/yy);
if(s.count(((long)(x-circle*xx) << 30) | (y-circle*yy)) == 0) return false;
for(auto v: obstacles){
if(v.size() != 2) continue;
if(v[0] > x || v[1] > y) continue;
circle = min(v[0]/xx,v[1]/yy);
if(s.count(((long)(v[0]-circle*xx) << 30) | (v[1]-circle * yy))) return false;
}
return true;
}
};
java 解法, 执行用时: 3 ms, 内存消耗: 40 MB, 提交时间: 2023-06-29 09:34:53
class Solution {
public boolean robot(String command, int[][] obstacles, int x, int y) {
int dx = 0, dy = 0;
char[] cmd = command.toCharArray(); // 把String转为数组，方便遍历。
for (char c : cmd) { // 算出up和right各有多少个。
if (c == 'U') dy++;
else dx++;
}
int ans = isPassed(cmd, x, y, dx, dy); // 拿到走到终点的次数。
// 先看isPassed函数再往下看。
/*
为什么isPassed要拿到走的总次数而不直接返回true或false呢
比如你发现有一个obstacle是经过的，那么最终答案并不一定是false，
因为如果终点在这个点的前面，那么机器人根本不会走到那个点。答案是true。
*/
if (ans == -1) return false; // 终点都没经过，肯定false
for (int[] obstacle : obstacles) {
int cnt = isPassed(cmd, obstacle[0], obstacle[1], dx, dy);
if (cnt != -1 && cnt < ans) return false;
//不等于-1，说明经过了，然后再看这个点和终点哪个次数多。ans多，说明这个点在ans前面，返回false。
}
return true;
}
// 判断是否经过该点，经过返回走的次数，没经过返回-1。
public int isPassed(char[] cmd, int x, int y, int dx, int dy) {
int round = Math.min(x / dx, y / dy); // 计算走到第x-1或y-1层需要多少轮
int cnt = cmd.length * round; // 前几轮的总次数
dx *= round; dy *= round; // 在第x-1或y-1层时的位置。
if (dx == x && dy == y) return cnt; // 正好就是要找的点，直接返回。
for (char c : cmd) { // 遍历第x层或y层，如果经过，那么答案一定会遍历到。
if (c == 'U') dy++; // 要按command的顺序走
else dx++;
cnt++; // 不要忘了每遍历一次，次数都要加1
if (dx == x && dy == y) return cnt; // 一旦找到，直接返回所需要的次数。
}
return -1;
}
}
python3 解法, 执行用时: 44 ms, 内存消耗: 16.5 MB, 提交时间: 2023-06-29 09:34:13
class Solution:
def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:
xi, yi = 0, 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
java 解法, 执行用时: 0 ms, 内存消耗: 40 MB, 提交时间: 2023-06-29 09:32:59
class Solution {
public boolean robot(String cmd, int[][] obstacles, int x, int y) {
int n = cmd.length();
int sx = 0, sy = 0;
// 记录走完一轮后机器人的位置
for (int i = 0; i < n; ++ i) {
char c = cmd.charAt(i);
if (c == 'U') ++ sy;
else ++ sx;
}
// 先计算能否到达终点 不考虑障碍物
// 若不能直接返回false
boolean canFinish = canReach(cmd, x, y, sx, sy);
if (!canFinish) return false;
// 判断在终点前会不会遇到障碍物
// 若遇到则返回false
for (int[] o : obstacles) {
if (o[0] > x || o[1] > y)
continue;
if (canReach(cmd, o[0], o[1], sx, sy)) return false;
}
return true;
}
// 判断能否从坐标(x, y)到达(tx, ty)
public boolean canReach(String cmd, int tx, int ty, int x, int y) {
// round记录走到目标点至少要走多少轮
int round = Math.min(tx/x, ty/y);
int nx = round*x, ny = round*y;
if (nx == tx && ny == ty) return true;
int n = cmd.length();
for (int i = 0; i < n; ++ i) {
char c = cmd.charAt(i);
if (c == 'U') ++ ny;
else ++ nx;
if (nx > tx || ny > ty) return false;
if (nx == tx && ny == ty) return true;
}
return true;
}
}