summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authordzwdz2022-12-12 18:49:13 +0100
committerdzwdz2022-12-12 18:49:13 +0100
commitc91c6347a0a63a7f14e12677be181546880d16ce (patch)
tree1151fc37c913e8e2119c42edacc37812a0789ac4
parent2571a014cac9c33aa10145c4019f40278a72659f (diff)
day 12 part 1
-rw-r--r--22.12/main.cpp81
1 files changed, 81 insertions, 0 deletions
diff --git a/22.12/main.cpp b/22.12/main.cpp
new file mode 100644
index 0000000..110cf15
--- /dev/null
+++ b/22.12/main.cpp
@@ -0,0 +1,81 @@
+#include <algorithm>
+#include <cstddef>
+#include <deque>
+#include <iostream>
+#include <string>
+using namespace std;
+
+static constexpr size_t w = 132, h = 42;
+static uint8_t heights[h][w];
+
+struct Point {int x, y, v;};
+Point start, goal;
+
+void
+readInput()
+{
+ for (auto &r : heights) {
+ fill(begin(r), end(r), 255);
+ }
+ int y = 0;
+ for (string line; getline(cin, line); ) {
+ if (h <= y) throw "bad input";
+ for (int x = 0; x < line.size(); x++) {
+ if (w <= x) throw "bad input";
+ char c = line[x];
+ if (c == 'S') {
+ start.x = x;
+ start.y = y;
+ start.v = 0;
+ c = 'a';
+ } else if (c == 'E') {
+ goal.x = x;
+ goal.y = y;
+ goal.v = 0; //unused
+ c = 'z';
+ }
+ heights[y][x] = c - 'a';
+ }
+ y++;
+ }
+}
+
+int
+part1()
+{
+ bool visited[h][w] = {0};
+ deque<Point> frontier;
+ frontier.push_back(start);
+
+ while (!frontier.empty()) {
+ Point p = frontier[0];
+ frontier.pop_front();
+ for (auto n : {
+ Point{p.x + 1, p.y , p.v + 1},
+ Point{p.x - 1, p.y , p.v + 1},
+ Point{p.x , p.y + 1, p.v + 1},
+ Point{p.x , p.y - 1, p.v + 1},
+ }) {
+ if (!(0 <= n.x && n.x < w && 0 <= n.y && n.y < h))
+ continue;
+ if (visited[n.y][n.x]) continue;
+ auto h1 = heights[p.y][p.x];
+ auto h2 = heights[n.y][n.x];
+ if (h1 + 1 < h2) continue;
+ visited[n.y][n.x] = true;
+ if (n.x == goal.x && n.y == goal.y) {
+ return n.v;
+ }
+ frontier.push_back(n);
+ // cout << n.x << " " << n.y << " " << n.v << endl;
+ }
+ }
+ return -1;
+}
+
+int
+main()
+{
+ readInput();
+ cout << part1() << endl;
+}