diff options
| -rw-r--r-- | 22.18/main.cpp | 54 |
1 files changed, 54 insertions, 0 deletions
diff --git a/22.18/main.cpp b/22.18/main.cpp index f4fbcea..eaf7bab 100644 --- a/22.18/main.cpp +++ b/22.18/main.cpp @@ -1,4 +1,6 @@ +#include <algorithm> #include <cstdio> +#include <deque> #include <string> #include <unordered_set> using namespace std; @@ -28,6 +30,10 @@ struct Vec3 z + o.z, }; } + + bool operator<(const Vec3& o) const { + return x < o.x || y < o.y || z < o.z; + } }; /* from nullprogram */ @@ -71,6 +77,53 @@ partOne(unordered_set<Vec3> const& map) } 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; @@ -80,4 +133,5 @@ main() map.insert(v); } printf("%d\n", partOne(map)); + printf("%d\n", partTwo(map)); } |