总体思路：模拟机器人行走的过程。一步一步走，如果下一步是障碍物，则停止移动，继续执行下一个命令。
怎么表示机器人移动的方向？
我们可以用一个向量数组
$$
\textit{dirs} = [(0, 1), (1, 0), (0, -1), (-1, 0)]
$$
分别表示顺时针的上右下左（北东南西）四个方向。
用一个下标 $k$ 表示当前机器人的方向为 $\textit{dirs}[k]$，初始 $k=0$，表示初始方向为上。
-
右转：也就是顺时针转 $90^\circ$，把 $k$ 增加一。如果 $k=4$，则绕回到 $\textit{dirs}$ 数组的最左边，即 $k$ 更新为 $0$。我们可以把 $k$ 统一更新为 $(k+1)\bmod 4$，这样可以兼容 $k=3$ 加一后变成 $0$ 的情况。
-
左转：也就是逆时针转 $90^\circ$，把 $k$ 减少一。如果 $k=0$，则绕回到 $\textit{dirs}$ 数组的最右边，即 $k$ 更新为 $3$。我们可以把 $k$ 统一更新为 $(k+3)\bmod 4$，这是因为 $\textit{dirs}$ 是个循环数组，一个元素的左边相邻元素，相当于往右数 $3$ 个元素。比如 $\textit{dirs}$ 中的 $(1,0)$ 往右数 $3$ 个元素，就是 $(0,1)$。
设 $c = \textit{commands}[i]$。当 $c>0$ 时，机器人要往 $\textit{dirs}[k]$ 方向移动 $c$ 个单位长度。一步一步移动，如果发现下一步是障碍物，则停止移动，继续执行下一个命令。
为了快速判断某个坐标是否为障碍物（是否在 $\textit{obstacles}$ 数组中），我们可以把 $\textit{obstacles}$ 转成哈希集合，判断坐标是否在哈希集合中。
注：可能起点也有障碍物，这相当于机器人站在障碍物上，是可以继续移动的。
写法一
###py
DIRS = (0, 1), (1, 0), (0, -1), (-1, 0) # 上右下左（顺时针）
class Solution:
def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
obstacle_set = set(map(tuple, obstacles))
ans = x = y = k = 0
for c in commands:
if c == -1: # 右转
k = (k + 1) % 4
elif c == -2: # 左转
k = (k + 3) % 4
else: # 直行
while c > 0 and (x + DIRS[k][0], y + DIRS[k][1]) not in obstacle_set:
x += DIRS[k][0]
y += DIRS[k][1]
c -= 1
ans = max(ans, x * x + y * y)
return ans
###java
class Solution {
private static final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 上右下左（顺时针）
public int robotSim(int[] commands, int[][] obstacles) {
HashSet<Integer> obstacleSet = new HashSet<>(obstacles.length, 1); // 预分配空间
final int OFFSET = (int) 3e4;
for (int[] p : obstacles) {
// p 是两个 16 位整数，合并成一个 32 位整数
obstacleSet.add((p[0] + OFFSET) << 16 | (p[1] + OFFSET));
}
int x = 0;
int y = 0;
int k = 0;
int ans = 0;
for (int c : commands) {
if (c == -1) { // 右转
k = (k + 1) % 4;
} else if (c == -2) { // 左转
k = (k + 3) % 4;
} else { // 直行
while (c-- > 0) {
int nx = x + DIRS[k][0];
int ny = y + DIRS[k][1];
if (obstacleSet.contains((nx + OFFSET) << 16 | (ny + OFFSET))) {
break;
}
x = nx;
y = ny;
}
ans = Math.max(ans, x * x + y * y);
}
}
return ans;
}
}
###cpp
class Solution {
static constexpr int DIRS[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 上右下左（顺时针）
public:
int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
unordered_set<int> obstacle_set;
obstacle_set.reserve(obstacles.size()); // 预分配空间
constexpr int OFFSET = 3e4;
for (auto& p : obstacles) {
// p 是两个 16 位整数，合并成一个 32 位整数
obstacle_set.insert((p[0] + OFFSET) << 16 | (p[1] + OFFSET));
}
int ans = 0, x = 0, y = 0, k = 0;
for (int c : commands) {
if (c == -1) { // 右转
k = (k + 1) % 4;
} else if (c == -2) { // 左转
k = (k + 3) % 4;
} else { // 直行
while (c--) {
int nx = x + DIRS[k][0];
int ny = y + DIRS[k][1];
if (obstacle_set.contains((nx + OFFSET) << 16 | (ny + OFFSET))) {
break;
}
x = nx;
y = ny;
}
ans = max(ans, x * x + y * y);
}
}
return ans;
}
};
###go
type pair struct{ x, y int }
var dirs = [...]pair{{0, 1}, {1, 0}, {0, -1}, {-1, 0}} // 上右下左（顺时针）
func robotSim(commands []int, obstacles [][]int) (ans int) {
isObstacle := make(map[pair]bool, len(obstacles)) // 预分配空间
for _, p := range obstacles {
isObstacle[pair{p[0], p[1]}] = true
}
x, y, k := 0, 0, 0
for _, c := range commands {
if c == -1 { // 右转
k = (k + 1) % 4
} else if c == -2 { // 左转
k = (k + 3) % 4
} else { // 直行
for ; c > 0 && !isObstacle[pair{x + dirs[k].x, y + dirs[k].y}]; c-- {
x += dirs[k].x
y += dirs[k].y
}
ans = max(ans, x*x+y*y)
}
}
return
}
写法二
设 $c = \textit{commands}[i]$。
- 右转时 $c=-1$，我们把 $k$ 增加了 $2c+3 = 1$。
- 左转时 $c=-2$，我们把 $k$ 增加了 $2c+3 = -1$。
因此，这两种情况可以进一步统一成，把 $k$ 更新成 $(k + 2c + 3)\bmod 4$。但是，当 $k=0$ 且 $2c+3=-1$ 时，$k + 2c + 3=-1$ 是负数。对于模 $4$ 运算，多增加 $4$ 不影响结果，所以可以把 $2c+3$ 改成 $2c+7$，也就把 $k$ 更新成
$$
(k + 2c + 7)\bmod 4
$$
###py
DIRS = (0, 1), (1, 0), (0, -1), (-1, 0) # 上右下左（顺时针）
class Solution:
def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
obstacle_set = set(map(tuple, obstacles))
ans = x = y = k = 0
for c in commands:
if c < 0:
k = (k + c * 2 + 7) % 4 # c=-2 左转，c=-1 右转
continue
while c > 0 and (x + DIRS[k][0], y + DIRS[k][1]) not in obstacle_set:
x += DIRS[k][0]
y += DIRS[k][1]
c -= 1
ans = max(ans, x * x + y * y)
return ans
###java
class Solution {
private static final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 上右下左（顺时针）
public int robotSim(int[] commands, int[][] obstacles) {
HashSet<Integer> obstacleSet = new HashSet<>(obstacles.length, 1); // 预分配空间
final int OFFSET = (int) 3e4;
for (int[] p : obstacles) {
// p 是两个 16 位整数，合并成一个 32 位整数
obstacleSet.add((p[0] + OFFSET) << 16 | (p[1] + OFFSET));
}
int x = 0;
int y = 0;
int k = 0;
int ans = 0;
for (int c : commands) {
if (c < 0) {
k = (k + c * 2 + 7) % 4; // c=-2 左转，c=-1 右转
continue;
}
while (c-- > 0) {
int nx = x + DIRS[k][0];
int ny = y + DIRS[k][1];
if (obstacleSet.contains((nx + OFFSET) << 16 | (ny + OFFSET))) {
break;
}
x = nx;
y = ny;
}
ans = Math.max(ans, x * x + y * y);
}
return ans;
}
}
###cpp
class Solution {
static constexpr int DIRS[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 上右下左（顺时针）
public:
int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
unordered_set<int> obstacle_set;
obstacle_set.reserve(obstacles.size()); // 预分配空间
constexpr int OFFSET = 3e4;
for (auto& p : obstacles) {
// p 是两个 16 位整数，合并成一个 32 位整数
obstacle_set.insert((p[0] + OFFSET) << 16 | (p[1] + OFFSET));
}
int ans = 0, x = 0, y = 0, k = 0;
for (int c : commands) {
if (c < 0) {
k = (k + c * 2 + 7) % 4; // c=-2 左转，c=-1 右转
continue;
}
while (c--) {
int nx = x + DIRS[k][0];
int ny = y + DIRS[k][1];
if (obstacle_set.contains((nx + OFFSET) << 16 | (ny + OFFSET))) {
break;
}
x = nx;
y = ny;
}
ans = max(ans, x * x + y * y);
}
return ans;
}
};
###go
type pair struct{ x, y int }
var dirs = [...]pair{{0, 1}, {1, 0}, {0, -1}, {-1, 0}} // 上右下左（顺时针）
func robotSim(commands []int, obstacles [][]int) (ans int) {
isObstacle := make(map[pair]bool, len(obstacles)) // 预分配空间
for _, p := range obstacles {
isObstacle[pair{p[0], p[1]}] = true
}
x, y, k := 0, 0, 0
for _, c := range commands {
if c < 0 {
k = (k + c*2 + 7) % 4 // c=-2 左转，c=-1 右转
continue
}
for ; c > 0 && !isObstacle[pair{x + dirs[k].x, y + dirs[k].y}]; c-- {
x += dirs[k].x
y += dirs[k].y
}
ans = max(ans, x*x+y*y)
}
return
}
复杂度分析
- 时间复杂度：$\mathcal{O}(nU + m)$，其中 $n$ 是 $\textit{commands}$ 的长度，$m$ 是 $\textit{obstacles}$ 的长度，$U=\max(\textit{commands})\le 9$。
- 空间复杂度：$\mathcal{O}(m)$。
分类题单
如何科学刷题？
- 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
- 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
- 单调栈（基础/矩形面积/贡献法/最小字典序）
- 网格图（DFS/BFS/综合应用）
- 位运算（基础/性质/拆位/试填/恒等式/思维）
- 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
- 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
- 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
- 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
- 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
- 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
- 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）
我的题解精选（已分类）
欢迎关注 B站@灵茶山艾府
登录
