题目描述
A robot on an infinite grid starts at point (0, 0) and faces north. The robot can receive one of three possible types of commands:
-2
: turn left 90 degrees-1
: turn right 90 degrees1 <= x <= 9
: move forwardx
units
Some of the grid squares are obstacles. The i
-th obstacle is at grid point (obstacles[i][0], obstacles[i][1])
If the robot would try to move onto them, the robot stays on the previous grid square instead (but still continues following the rest of the route.) Return the square of the maximum Euclidean distance that the robot will be from the origin.
Example 1:
Input: commands = [4,-1,3], obstacles = []
Output: 25
Explanation: robot will go to (3, 4)
Example 2:
Input: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
Output: 65
Explanation: robot will be stuck at (1, 4) before turning left and going to (1, 8)
Note:
0 <= commands.length <= 10000
0 <= obstacles.length <= 10000
-30000 <= obstacle[i][0] <= 30000
-30000 <= obstacle[i][1] <= 30000
- The answer is guaranteed to be less than
2 ^ 31
.
题意:机器人在一个无限大小的网格上行走,从点 (0, 0)
处开始出发,面向北方。该机器人可以接收以下三种类型的命令:
-2:向左转 90 度
-1:向右转 90 度
1 <= x <= 9:向前移动x
个单位长度
在网格上有一些格子被视为障碍物。第i
个障碍物位于网格点(obstacles[i][0], obstacles[i][1])
如果机器人试图走到障碍物上方,那么它将停留在障碍物的前一个网格方块上,但仍然可以继续该路线的其余部分。返回从原点到机器人的最大欧式距离的平方。
题解:模拟。为了编码直观,我是用了枚举类型来标记方向,然后使用哈希表存储每一行的障碍的纵坐标。注意一下左转和右转的时候,方向变化的公式,这个公式在很多顺时针逆时针题目中都会遇到。
int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
enum direction{up,right,down,left};
unordered_map<int,set<int>> hash;
for(auto p : obstacles)
hash[p[0]].insert(p[1]);
int state = up,r = 0,c = 0,res = 0,n = commands.size();
for(int i = 0 ; i < n ; i ++)
{
if(commands[i] == -1) state = (state + 1) % 4;
else if(commands[i] == -2) state = (state + 4 - 1) % 4;
else
{
int j;
if(state == up)
{
for(j = 1 ; j <= commands[i] ; j ++)
if(hash[r].count(c + j))
break;
c += j - 1;
}else if(state == down)
{
for(j = 1 ; j <= commands[i] ; j ++)
if(hash[r].count(c - j))
break;
c -= (j - 1);
}else if(state == left)
{
for(j = 1 ; j <= commands[i] ; j ++)
if(hash[r - j].count(c))
break;
r -= (j - 1);
}else
{
for(j = 1 ; j <= commands[i] ; j ++)
if(hash[r + j].count(c))
break;
r += (j - 1);
}
res = max(res,r * r + c * c);
}
}
return res;
}