机器人在一个无限大小的 XY 网格平面上行走，从点 (0, 0) 处开始出发，面向北方。该机器人可以接收以下三种类型的命令 commands ：
-2：向左转90度-1：向右转90度1 <= x <= 9：向前移动x个单位长度
在网格上有一些格子被视为障碍物 obstacles 。第 i 个障碍物位于网格点 obstacles[i] = (xi, yi) 。
机器人无法走到障碍物上，它将会停留在障碍物的前一个网格方块上，并继续执行下一个命令。
返回机器人距离原点的 最大欧式距离 的 平方 。（即，如果距离为 5 ，则返回 25 ）
注意：
- 北方表示 +Y 方向。
- 东方表示 +X 方向。
- 南方表示 -Y 方向。
- 西方表示 -X 方向。
- 原点 [0,0] 可能会有障碍物。
示例 1：
输入：commands = [4,-1,3], obstacles = [] 输出：25 解释： 机器人开始位于 (0, 0)： 1. 向北移动 4 个单位，到达 (0, 4) 2. 右转 3. 向东移动 3 个单位，到达 (3, 4) 距离原点最远的是 (3, 4) ，距离为 32 + 42 = 25
示例 2：
输入：commands = [4,-1,4,-2,4], obstacles = [[2,4]] 输出：65 解释：机器人开始位于 (0, 0)： 1. 向北移动 4 个单位，到达 (0, 4) 2. 右转 3. 向东移动 1 个单位，然后被位于 (2, 4) 的障碍物阻挡，机器人停在 (1, 4) 4. 左转 5. 向北走 4 个单位，到达 (1, 8) 距离原点最远的是 (1, 8) ，距离为 12 + 82 = 65
示例 3：
输入：commands = [6,-1,-1,6], obstacles = [] 输出：36 解释：机器人开始位于 (0, 0): 1. 向北移动 6 个单位，到达 (0, 6). 2. 右转 3. 右转 4. 向南移动 6 个单位，到达 (0, 0). 机器人距离原点最远的点是 (0, 6)，其距离的平方是 62 = 36 个单位。
提示：
1 <= commands.length <= 104commands[i]的值可以取-2、-1或者是范围[1, 9]内的一个整数。0 <= obstacles.length <= 104-3 * 104 <= xi, yi <= 3 * 104- 答案保证小于
231
我们定义一个长度为
我们使用一个哈希表
另外，使用两个变量
接下来，我们遍历数组
- 如果
$c = -2$ ，表示机器人向左转$90$ 度，即$k = (k + 3) \bmod 4$ ； - 如果
$c = -1$ ，表示机器人向右转$90$ 度，即$k = (k + 1) \bmod 4$ ； - 否则，表示机器人向前移动
$c$ 个单位长度。我们将机器人当前的方向$k$ 与方向数组$dirs$ 结合，即可得到机器人在$x$ 轴和$y$ 轴上的增量。我们将$c$ 个单位长度的增量分别累加到$x$ 和$y$ 上，并判断每次移动后的新坐标$(nx, ny)$ 是否在障碍物的坐标中，如果不在，则更新答案$ans$ ，否则停止模拟，进行下一条指令的模拟。
最后返回答案
时间复杂度
class Solution:
def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
dirs = (0, 1, 0, -1, 0)
s = {(x, y) for x, y in obstacles}
ans = k = 0
x = y = 0
for c in commands:
if c == -2:
k = (k + 3) % 4
elif c == -1:
k = (k + 1) % 4
else:
for _ in range(c):
nx, ny = x + dirs[k], y + dirs[k + 1]
if (nx, ny) in s:
break
x, y = nx, ny
ans = max(ans, x * x + y * y)
return ansclass Solution {
public int robotSim(int[] commands, int[][] obstacles) {
int[] dirs = {0, 1, 0, -1, 0};
Set<Integer> s = new HashSet<>(obstacles.length);
for (var e : obstacles) {
s.add(f(e[0], e[1]));
}
int ans = 0, k = 0;
int x = 0, y = 0;
for (int c : commands) {
if (c == -2) {
k = (k + 3) % 4;
} else if (c == -1) {
k = (k + 1) % 4;
} else {
while (c-- > 0) {
int nx = x + dirs[k], ny = y + dirs[k + 1];
if (s.contains(f(nx, ny))) {
break;
}
x = nx;
y = ny;
ans = Math.max(ans, x * x + y * y);
}
}
}
return ans;
}
private int f(int x, int y) {
return x * 60010 + y;
}
}class Solution {
public:
int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
int dirs[5] = {0, 1, 0, -1, 0};
auto f = [](int x, int y) {
return x * 60010 + y;
};
unordered_set<int> s;
for (auto& e : obstacles) {
s.insert(f(e[0], e[1]));
}
int ans = 0, k = 0;
int x = 0, y = 0;
for (int c : commands) {
if (c == -2) {
k = (k + 3) % 4;
} else if (c == -1) {
k = (k + 1) % 4;
} else {
while (c--) {
int nx = x + dirs[k], ny = y + dirs[k + 1];
if (s.count(f(nx, ny))) {
break;
}
x = nx;
y = ny;
ans = max(ans, x * x + y * y);
}
}
}
return ans;
}
};func robotSim(commands []int, obstacles [][]int) (ans int) {
dirs := [5]int{0, 1, 0, -1, 0}
type pair struct{ x, y int }
s := map[pair]bool{}
for _, e := range obstacles {
s[pair{e[0], e[1]}] = true
}
var x, y, k int
for _, c := range commands {
if c == -2 {
k = (k + 3) % 4
} else if c == -1 {
k = (k + 1) % 4
} else {
for ; c > 0 && !s[pair{x + dirs[k], y + dirs[k+1]}]; c-- {
x += dirs[k]
y += dirs[k+1]
ans = max(ans, x*x+y*y)
}
}
}
return
}function robotSim(commands: number[], obstacles: number[][]): number {
const dirs = [0, 1, 0, -1, 0];
const s: Set<number> = new Set();
const f = (x: number, y: number) => x * 60010 + y;
for (const [x, y] of obstacles) {
s.add(f(x, y));
}
let [ans, x, y, k] = [0, 0, 0, 0];
for (let c of commands) {
if (c === -2) {
k = (k + 3) % 4;
} else if (c === -1) {
k = (k + 1) % 4;
} else {
while (c-- > 0) {
const [nx, ny] = [x + dirs[k], y + dirs[k + 1]];
if (s.has(f(nx, ny))) {
break;
}
[x, y] = [nx, ny];
ans = Math.max(ans, x * x + y * y);
}
}
}
return ans;
}