# 874. Walking Robot Simulation 模拟行走机器人

@TOC

## # 题目描述

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(object):
def robotSim(self, commands, obstacles):
"""
:type commands: List[int]
:type obstacles: List[List[int]]
:rtype: int
"""
# directions = ['N', 'E', 'S', 'W']
# 0 - N, 1 - E, 2 - S, 3 - W
position_offset = [(0, 1), (1, 0), (0, -1), (-1, 0)]
obstacles = set(map(tuple, obstacles))
x, y, direction, max_distance = 0, 0, 0, 0
for command in commands:
if command == -2: direction = (direction - 1) % 4
elif command == -1: direction = (direction + 1) % 4
else:
x_off, y_off = position_offset[direction]
while command:
if (x + x_off, y + y_off) not in obstacles:
x += x_off
y += y_off
command -= 1
max_distance = max(max_distance, x**2 + y**2)
print(x, y)
return max_distance
``````

``````class Solution {
public:
int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
int res = 0;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
set<pair<int, int>> obs;
for (auto ob : obstacles) {
obs.insert(make_pair(ob[0], ob[1]));
}
int x = 0, y = 0;
int d = 0;
for (int command : commands) {
if (command == -1) {
d = (d + 1) % 4;
} else if (command == -2) {
d = (d + 3) % 4;
} else {
while (command--){
int nx = x + dx[d];
int ny = y + dy[d];
if (obs.find(make_pair(nx, ny)) != obs.end()){
break;
}
x = nx;
y = ny;
res = max(res, x * x + y * y);
}
}
}
return res;
}
};
``````

https://leetcode.com/problems/walking-robot-simulation/discuss/157505/Simple-Python-solution-Accepted

## # 日期

2018 年 9 月 3 日 ———— 新学期开学第一天！