题目
机器人在一个无限大小的 XY 网格平面上行走，从点?(0, 0) 处开始出发，面向北方。该机器人可以接收以下三种类型的命令 commands ：
????????-2 ：向左转?90 度
????????-1 ：向右转 90 度
????????1 <= x <= 9 ：向前移动?x?个单位长度
在网格上有一些格子被视为障碍物?obstacles 。第 i?个障碍物位于网格点 ?obstacles[i] = (xi, yi) 。
机器人无法走到障碍物上，它将会停留在障碍物的前一个网格方块上，但仍然可以继续尝试进行该路线的其余部分。
返回从原点到机器人所有经过的路径点（坐标为整数）的最大欧式距离的平方。（即，如果距离为 5 ，则返回 25 ）
注意：
????????北表示 +Y 方向。
????????东表示 +X 方向。
????????南表示 -Y 方向。
????????西表示 -X 方向。
提示：
????????1 <= commands.length <= 104
????????commands[i] is one of the values in the list [-2,-1,1,2,3,4,5,6,7,8,9].
????????0 <= obstacles.length <= 104
????????-3 * 104 <= xi, yi <= 3 * 104
????????答案保证小于 2^31
解题思路：
暴力解法时间复杂度O(n^2),此题为判断下一步移动位置是否障碍数组中，也就是查找数组中的元素，若用数组进行查找是O(n)的时间复杂度，且每次遍历都要查询时间复杂度会变为O(n^2)。故我们用无序集合替代数组降低时间复杂度。使用方向数组简化网格内行走问题。
代码示例：
//无序集合 + hash,暴力解法n*n
int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
unordered_set<long long> set;//更快的在一个容器中某个元素在不在的问题 O(1)的查找
for(const auto& obstacle : obstacles)
{
set.insert(calhash(obstacle));
}
int x = 0, y= 0;//定义坐标
int dir = 0;//定义方向 N=0,,E=1,S=2,W=3
//技巧，网格中行走题目 定义方向数组
const int dx[4] = {0, 1, 0, -1};//此处是依据空间中xy坐标系北东南西方向
const int dy[4] = {1, 0, -1, 0};
int ans = 0;
for(int command : commands)
{
if(command == -1)
{
dir = (dir + 1) % 4;
}
else if(command == -2)
{
dir = (dir + 3) % 4;
}
else
{
for(int i = 0; i < command; ++i)
{
int nx = x + dx[dir];
int ny = y + dy[dir];
//判断下一步是不是障碍物
if(set.find(calhash({nx,ny})) != set.end()) break;
x = nx;
y = ny;
ans = max(ans, x * x + y * y);
}
}
}
return ans;
}
private:
long long calhash(const vector<int>& obstacle)
{
//行号乘列号加列数 注：这块也可以用其他的hash算法
//细节 long long 类型，因为乘完之后数据超出int范围,如果60001后不加ll则不会返回long long
return (obstacle[0] + 30000)*60001ll + (obstacle[1] + 30000);
};
结果输出：
输入：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
|