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
113
114
115
116
117
118
119
120
121
122
123
|
//#define _GNU_SOURCE
#include <ctype.h>
#include <search.h>
#include <stdio.h>
#include <stdlib.h>
struct point {
int x;
int y;
};
struct point *
point_copy(struct point const * other)
{
struct point * p = malloc(sizeof(struct point));
if (!p)
return NULL;
p->x = other->x;
p->y = other->y;
return p;
}
int
point_cmp(struct point const * a, struct point const * b)
{
return a->x - b->x != 0
? a->x - b->x
: a->y - b->y;
}
int
point_tcmp(void const * a, void const * b)
{
return point_cmp(a, b);
}
int
main()
{
char buf[BUFSIZ];
struct point head = {0}, * tail = point_copy(&head);
void * tails = NULL;
int ntails = 0;
tsearch(tail, &tails, point_tcmp);
tail = point_copy(tail);
++ntails;
while (fgets(buf, sizeof(buf), stdin)) {
int dist, dx, dy;
if (!isalpha(buf[0])
|| buf[1] != ' '
|| !isdigit(buf[2]))
{
fprintf(stderr, "Unexpected input: %s\n", buf);
return -1;
}
dist = atoi(buf + 2);
if (dist == 0) {
fprintf(stderr, "Unexpected distance in: %s\n", buf);
// Allow 0 for now...
}
switch (buf[0]) {
case 'L': head.x -= dist; break;
case 'R': head.x += dist; break;
case 'U': head.y += dist; break;
case 'D': head.y -= dist; break;
default:
fprintf(stderr, "Unexpected input: %s\n", buf);
return -1;
}
dx = head.x - tail->x;
dy = head.y - tail->y;
while (dx * dx + dy * dy > 2) {
struct point ** pp;
if (dx > 0) {
++tail->x;
--dx;
}
if (dx < 0) {
--tail->x;
++dx;
}
if (dy > 0) {
++tail->y;
--dy;
}
if (dy < 0) {
--tail->y;
++dy;
}
// Search/insert current tail in visited tails
pp = tsearch(tail, &tails, point_tcmp);
if (*pp == tail) {
// This was a new one, tail is now in the tree
tail = point_copy(tail);
++ntails;
}
}
}
printf("Unique tail spots visited: %d\n", ntails);
free(tail);
#ifdef _GNU_SOURCE
tdestroy(tails, free);
#endif
return 0;
}
|
