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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
// 874. Walking Robot Simulation
#include "leetcode.h"
/*
* a robot on an infinite xy plane starts at point '(0, 0)' facing north. the
* robot can receive a sequence of these three possible types of 'commands': -2
* turn left 90 degree, -1 turn right 90 degrees, '1 <= k <= 9' move forward 'k'
* units, one unit at a time. some of the grid squares are 'obstacles'. the i'th
* obstacle is at grid point 'obstacles[i] = (xi, yi)'. if the robot runs into
* an obstacle, then it will instead stay in its current location and move on to
* the next command. return the maximum euclidean distance that the robot ever
* gets from the origin squared.
*/
enum directions { NORTH, EAST, SOUTH, WEST, INVALID };
inline int change_direction(int old, int turn) {
switch (old) {
case NORTH:
return turn == -2 ? WEST : EAST;
case EAST:
return turn == -2 ? NORTH : SOUTH;
case SOUTH:
return turn == -2 ? EAST : WEST;
case WEST:
return turn == -2 ? SOUTH : NORTH;
default:
break;
}
return INVALID;
}
inline void move_forward(int *pos, int dir, int steps) {
switch (dir) {
case NORTH:
pos[1] += steps;
break;
case EAST:
pos[0] += steps;
break;
case SOUTH:
pos[1] -= steps;
break;
case WEST:
pos[0] -= steps;
break;
default:
break;
}
}
int robotSim(int *commands, int commandsSize, int **obstacles,
int obstaclesSize, int *obstaclesColSize) {
int pos[2] = {0, 0}, dir = NORTH, max_dist = 0;
for (int i = 0; i < commandsSize; i++) {
if (commands[i] == -2 || commands[i] == -1)
dir = change_direction(dir, commands[i]);
else {
int steps = commands[i], curr_dist = 0;
for (int j = 0; j < obstaclesSize; j++) {
if (dir == NORTH || dir == SOUTH) {
int obst_dist = (int)abs(obstacles[j][1] - pos[1]);
if ((obstacles[j][0] == pos[0]) &&
((dir == NORTH && obstacles[j][1] > pos[1]) ||
(dir == SOUTH && obstacles[j][1] < pos[1])) &&
(obst_dist <= steps)) {
steps = obst_dist - 1;
break;
}
} else {
int obst_dist = (int)abs(obstacles[j][0] - pos[0]);
if ((obstacles[j][1] == pos[1]) &&
((dir == EAST && obstacles[j][0] > pos[0]) ||
(dir == WEST && obstacles[j][0] < pos[0])) &&
(obst_dist <= steps)) {
steps = obst_dist - 1;
break;
}
}
}
move_forward(pos, dir, steps);
curr_dist = (pos[0] * pos[0]) + (pos[1] * pos[1]);
if (curr_dist > max_dist)
max_dist = curr_dist;
}
}
return max_dist;
}
int main() {
int c1[] = {4, -1, 3}, o1[1][0] = {{}}, ocs1[] = {1};
int c2[] = {4, -1, 4, -2, 4}, o2[1][2] = {{2, 4}}, ocs2[] = {1};
int c3[] = {6, -1, -1, 6}, o3[1][0] = {{}}, ocs3[] = {1};
printf("%d\n", robotSim(c1, ARRAY_SIZE(c1), (int **)o1, ARRAY_SIZE(o1),
ocs1)); // expect: 25
printf("%d\n", robotSim(c2, ARRAY_SIZE(c2), (int **)o2, ARRAY_SIZE(o2),
ocs2)); // expect: 65
printf("%d\n", robotSim(c3, ARRAY_SIZE(c3), (int **)o3, ARRAY_SIZE(o3),
ocs3)); // expect: 36
}
|