模拟行走机器人【LC874】
机器人在一个无限大小的 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 1 2 3分别表示北、东、南、西，假设此时方向为
dir，那么
- 如果没有障碍物，那么向指定方向移动，并求出该位置与原点的距离，判断是否需要更新；否则，停止移动
- 实现
class Solution { public int robotSim(int[] commands, int[][] obstacles) { int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};// -1 方向坐标右移，-2方向坐标左移 // 如何判断在移动过程中是否遇到障碍物，1<= x<=9，将障碍物存储在哈希表中，逐个判断 // 二维-> 一维 (数据范围：6 * 10^4 *6 * 10^4) Set<Integer> obs = new HashSet<>(); int n = 30000; int res = 0, i = 0; int x = 0, y = 0; for (int[] o : obstacles){ obs.add(o[0] * n + o[1]); } for (int c : commands){ if (c == -1){ i = (i + 1) % 4; }else if (c == -2){ i = (i + 3) % 4; }else{ int j = 0; while (j < c){ int newX = x + dirs[i][0], newY = y + dirs[i][1]; if (!obs.contains(newX * n + newY)){ res = Math.max(res, newX * newX + newY * newY); x = newX; y = newY; } j++; } } } return res; } }
