day 12 part 1

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;
+}