blob: e117bafd98b6fe26ef6f0bc65815b164bbe043cc (
plain)
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
101
102
103
104
105
106
107
108
109
110
111
112
|
// 818. Race Car
#include "leetcode.h"
/*
* your car starts at position 0 and speed +1 on an infinite number line. your
* car can go into negative positions. your car drives automatically according
* to a sequence of instructions 'A' (accelerate), and 'R' (reverse). given a
* target position 'target', return the length of the shortest sequence of
* instructions to get there.
*/
#define MAX_POW_2 20
struct args {
int position;
int speed;
};
struct queue {
struct args *a;
int prev;
int curr;
size_t len;
};
int *get_pow_2(void) {
int *res = (int *)malloc(2 * MAX_POW_2 * sizeof(int));
res[0] = 1;
for (int i = 1; i < MAX_POW_2; ++i)
res[i] = res[i - 1] * 2;
res[MAX_POW_2] = -1;
for (int i = MAX_POW_2 + 1; i < MAX_POW_2 * 2; ++i)
res[i] = res[i - 1] * 2;
return res;
}
void queue_init(struct queue *q) {
q->a = (struct args *)malloc(128 * sizeof(struct args *));
q->len = 128;
q->prev = -1;
q->curr = 0;
}
void queue_push(struct queue *q, struct args a) {
q->prev++;
if (q->prev >= q->len) {
q->a = (struct args *)realloc(q->a, 2 * q->len * sizeof(struct args));
q->len *= 2;
}
q->a[q->prev] = a;
}
struct args queue_pop(struct queue *q) {
struct args res = q->a[q->curr];
q->curr++;
return res;
}
bool queue_empty(struct queue *q) { return q->curr > q->prev || q->prev == -1; }
void queue_free(struct queue *q) { free(q->a); }
int racecar(int target) {
int *pow = get_pow_2();
int row_size = 2 * target + 1;
int col_size = 2 * MAX_POW_2;
int *vis[row_size];
for (int i = 0; i < row_size; ++i) {
vis[i] = (int *)malloc(col_size * sizeof(int));
memset(vis[i], -1, col_size * sizeof(int));
}
struct queue q;
queue_init(&q);
struct args initial;
initial.position = 0;
initial.speed = 0;
vis[initial.position][initial.speed] = 0;
queue_push(&q, initial);
while (!queue_empty(&q)) {
struct args curr = queue_pop(&q);
if (curr.position + pow[curr.speed] < row_size &&
curr.position + pow[curr.speed] >= 0 &&
vis[curr.position + pow[curr.speed]][1 + curr.speed] == -1) {
vis[curr.position + pow[curr.speed]][1 + curr.speed] =
vis[curr.position][curr.speed] + 1;
if (curr.position + pow[curr.speed] == target)
return vis[curr.position + pow[curr.speed]][1 + curr.speed];
struct args next;
next.position = curr.position + pow[curr.speed];
next.speed = curr.speed + 1;
queue_push(&q, next);
}
int change = curr.speed < MAX_POW_2 ? MAX_POW_2 : 0;
if (vis[curr.position][change] == -1) {
vis[curr.position][change] = vis[curr.position][curr.speed] + 1;
struct args next;
next.position = curr.position;
next.speed = change;
queue_push(&q, next);
}
}
for (int i = 0; i < row_size; i++)
free(vis[i]);
free(pow);
queue_free(&q);
return -1;
}
int main() {
printf("%d\n", racecar(3)); // expect: 2
printf("%d\n", racecar(6)); // expect: 5
}
|