# 874. Walking Robot Simulation

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 degrees
• `1 <= x <= 9`: move forward `x` 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:

1. `0 <= commands.length <= 10000`
2. `0 <= obstacles.length <= 10000`
3. `-30000 <= obstacle[i][0] <= 30000`
4. `-30000 <= obstacle[i][1] <= 30000`
5. The answer is guaranteed to be less than `2 ^ 31`.

``````class Solution {
public:
int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
int res = 0, x = 0, y = 0, idx = 0;
unordered_set<string> obs;
for (auto a : obstacles) obs.insert(to_string(a[0]) + "-" + to_string(a[1]));
vector<int> dirX{0, 1, 0, -1}, dirY{1, 0, -1, 0};
for (int command : commands) {
if (command == -1) idx = (idx + 1) % 4;
else if (command == -2) idx = (idx - 1 + 4) % 4;
else {
while (command-- > 0 && !obs.count(to_string(x + dirX[idx]) + "-" + to_string(y + dirY[idx]))) {
x += dirX[idx];
y += dirY[idx];
}
}
res = max(res, x * x + y * y);
}
return res;
}
};
``````

``````class Solution {
public:
int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
int res = 0, x = 0, y = 0, idx = 0;
set<pair<int, int>> obs;
for (auto a : obstacles) obs.insert({a[0], a[1]});
vector<int> dirX{0, 1, 0, -1}, dirY{1, 0, -1, 0};
for (int command : commands) {
if (command == -1) idx = (idx + 1) % 4;
else if (command == -2) idx = (idx - 1 + 4) % 4;
else {
while (command-- > 0 && !obs.count({x + dirX[idx], y + dirY[idx]})) {
x += dirX[idx];
y += dirY[idx];
}
}
res = max(res, x * x + y * y);
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/874

Robot Room Cleaner

https://leetcode.com/problems/walking-robot-simulation/

https://leetcode.com/problems/walking-robot-simulation/discuss/152322/Maximum!-This-is-crazy!

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation