题目地址：https://leetcode.com/problems/walking-robot-simulation/description/
题目描述
Arobot 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.
Thei-th obstacle is at grid point (obstacles[i][0], obstacles[i][1])
Ifthe 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、 Theanswerisguaranteedtobelessthan2^31.；
题目大意
一个机器人初始位置在（0,0）坐标，面朝北边。下面的移动方式是按照command来操作的，如果command==-2，左转；如果command==-1，右转；如果其他的正值，就对应了向前移动对应的步数。
另外，某些位置上会有障碍物，遇到障碍物他就只能停在前一个位置，等着下一个操作。
最后求，这个机器人离原点的坐标的笛卡尔距离的平方最大值，即max(x^2 + y^2)。
解题方法
模拟
按照这个操作如实的过一遍就行了，这里边难点是怎么判断障碍物，其实最直接的方法就是一步一步的移动，然后判断是否有障碍物，同时在每个位置都去计算距离的最大值。判断障碍物使用set可以做到线性时间复杂度。
整个算法的时间复杂度是O(MN)，其中M是命令数，N是障碍物数。在题目中估算大概是1亿的样子，没想到这样也能过。
代码如下：
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
二刷使用C++写了一遍，python支持列表的负索引，但是C++数组是不支持的，所以求下一个方向移动的时候，需要使用+3代替-1.
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;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
参考资料：
https://leetcode.com/problems/walking-robot-simulation/discuss/157505/Simple-Python-solution-Accepted
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发