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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
|
#include <algorithm>
#include <cstdio>
#include <deque>
#include <string>
#include <unordered_set>
using namespace std;
struct Vec3
{
int x, y, z;
bool operator==(const Vec3& o) const {
return o.x == x && o.y == y && o.z == z;
}
int& operator[](int idx) {
switch (idx) {
case 0: return x;
case 1: return y;
case 2: return z;
default:
throw "whatever";
}
}
Vec3 operator+(const Vec3& o) const {
return {
x + o.x,
y + o.y,
z + o.z,
};
}
bool operator<(const Vec3& o) const {
return x < o.x || y < o.y || z < o.z;
}
};
/* from nullprogram */
uint32_t
lowbias32(uint32_t x)
{
x ^= x >> 16;
x *= 0x7feb352dU;
x ^= x >> 15;
x *= 0x846ca68bU;
x ^= x >> 16;
return x;
}
template<>
struct std::hash<Vec3>
{
size_t operator()(Vec3 const& v) const noexcept {
int h = 0;
h = lowbias32(h ^ v.x);
h = lowbias32(h ^ v.y);
h = lowbias32(h ^ v.z);
return h;
}
};
int
partOne(unordered_set<Vec3> const& map)
{
int total = 0;
for (auto &v : map) {
for (int axis = 0; axis < 3; axis++) {
for (auto ad : {-1, 1}) {
Vec3 vd = v;
vd[axis] += ad;
if (map.count(vd) == 0) total++;
}
}
}
return total;
}
int
partTwo(unordered_set<Vec3> const& map)
{
Vec3 low = *map.begin();
Vec3 high = *map.begin();
for (auto &v : map) {
low = {
min(low.x, v.x),
min(low.y, v.y),
min(low.z, v.z),
};
high = {
max(high.x, v.x),
max(high.y, v.y),
max(high.z, v.z),
};
}
low = low + Vec3{-1, -1, -1};
high = high + Vec3{1, 1, 1};
int total = 0;
unordered_set<Vec3> visited;
deque<Vec3> frontier;
visited.insert(low);
frontier.push_back(low);
while (!frontier.empty()) {
Vec3 v = frontier.front();
frontier.pop_front();
for (int axis = 0; axis < 3; axis++) {
for (auto ad : {-1, 1}) {
Vec3 vd = v;
vd[axis] += ad;
if (vd < low || high < vd) continue;
if (visited.count(vd) == 1) continue;
if (map.count(vd) == 1) {
total += 1;
} else {
visited.insert(vd);
frontier.push_back(vd);
}
}
}
}
return total;
}
int
main()
{
int x, y, z;
unordered_set<Vec3> map;
while (scanf("%d,%d,%d ", &x, &y, &z) == 3) {
Vec3 v = {x, y, z};
map.insert(v);
}
printf("%d\n", partOne(map));
printf("%d\n", partTwo(map));
}
|
