贪心算法——模拟机器人行走（LeetCode874）

一、模拟机器人行走

题目如下：

题目来源：力扣（LeetCode）
原题链接：https://leetcode-cn.com/problems/walking-robot-simulation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、题目解析

对于题目中的实例2，机器人的行走路线如下图所示：

对于本题，情况稍微有点复杂，所以我们可以分以下三个步骤由简向繁，逐步完成。

步骤1：假设没有障碍物，模拟机器人行走

C++解法：

class Solution {
public: int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) { int n = commands.size(); int grad = 0; //方向向北 int x=0, y=0; //初始化点坐标 int dis_max=0; //最远点距离 for(int i=0; i<n; ++i) { if(commands[i]==-2) grad += 3; //向左转90度，即向右转270度，加3。 else if(commands[i]==-1) grad += 1; //向右转90度，加1 else //否则，就是正常移动 { grad = grad % 4; if(grad==0) //向北移动commands[i] y += commands[i]; else if(grad==1) //向东移动commands[i] x += commands[i]; else if(grad==2) //向南移动commands[i] y -= commands[i]; else //向西移动commands[i] x -= commands[i]; int dis = pow(x,2)+pow(y,2); dis_max = max(dis_max, dis); } } return dis_max; }
};

  

 

  
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
 

步骤2：当有障碍物时，模拟机器人行走

C++解法：

class Solution {
public: int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) { int n = commands.size(); int m = obstacles.size(); int grad = 0; //方向向北 int x=0, y=0; //初始化点坐标 int dis_max=0; //最远点距离 set<pair<int, int>> obstacleSet; for(int i=0; i<m; i++) obstacleSet.insert(make_pair(obstacles[i][0], obstacles[i][1])); for(int i=0; i<n; ++i) { if(commands[i]==-2) grad += 3; //向左转90度，即向右转270度，加3。 else if(commands[i]==-1) grad += 1; //向右转90度，加1 else //否则，就是正常移动 { grad = grad % 4; if(grad==0) //向北移动commands[i] { for(int j=0; j<commands[i]; ++j) { y += 1; if(obstacleSet.find(make_pair(x, y)) != obstacleSet.end()) //（x,y）是障碍点 { y -= 1; break; } } } else if(grad==1) //向东移动commands[i] { for(int j=0; j<commands[i]; ++j) { x += 1; if(obstacleSet.find(make_pair(x, y)) != obstacleSet.end()) { x -= 1; break; } } } else if(grad==2) //向南移动commands[i] { for(int j=0; j<commands[i]; ++j) { y -= 1; if(obstacleSet.find(make_pair(x, y)) != obstacleSet.end()) { y += 1; break; } } } else //向西移动commands[i]    { for(int j=0; j<commands[i]; ++j) { x -= 1; if(obstacleSet.find(make_pair(x, y)) != obstacleSet.end()) { x += 1; break; } } } int dis = pow(x,2)+pow(y,2); dis_max = max(dis_max, dis); } } return dis_max; }
};

  

 

  
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
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
 

提交结果：

步骤3：进一步优化

C++解法：

class Solution {
public: int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) { int n = commands.size(); int m = obstacles.size(); int grad = 0; //方向向北 int x=0, y=0; //初始化点坐标 int dis_max=0; //最远点距离 int grad_x[4] = {0, 1, 0, -1}; int grad_y[4] = {1, 0, -1, 0}; set<pair<int, int>> obstacleSet; for(int i=0; i<m; i++) obstacleSet.insert(make_pair(obstacles[i][0], obstacles[i][1])); for(int i=0; i<n; ++i) { if(commands[i]==-2) grad += 3; //向左转90度，即向右转270度，加3。 else if(commands[i]==-1) grad += 1; //向右转90度，加1 else //否则，就是正常移动 { grad = grad % 4; for(int j=0; j<commands[i]; ++j) { x += grad_x[grad]; y += grad_y[grad]; if(obstacleSet.find(make_pair(x, y)) != obstacleSet.end()) { x -= grad_x[grad]; y -= grad_y[grad]; break; } } int dis = pow(x,2)+pow(y,2); dis_max = max(dis_max, dis); } } return dis_max; }
};

  

 

  
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
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
 

提交结果：

文章来源: ai-wx.blog.csdn.net，作者：AI 菌，版权归原作者所有，如需转载，请联系作者。

原文链接：ai-wx.blog.csdn.net/article/details/117251634