From 26dd7e867ab392771b4b9a095ac409a18b5e7a71 Mon Sep 17 00:00:00 2001
From: dzwdz
Date: Mon, 12 Dec 2022 18:50:39 +0100
Subject: day 12 part 2

---
 22.12/main.cpp | 32 ++++++++++++++++++++++++++++++++
 1 file changed, 32 insertions(+)

(limited to '22.12/main.cpp')

diff --git a/22.12/main.cpp b/22.12/main.cpp
index 110cf15..5c7519e 100644
--- a/22.12/main.cpp
+++ b/22.12/main.cpp
@@ -73,9 +73,41 @@ part1()
 	return -1;
 }
 
+int
+part2()
+{
+	bool visited[h][w] = {0};
+	deque<Point> frontier;
+	frontier.push_back(goal);
+
+	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 (h2 + 1 < h1) continue;
+			visited[n.y][n.x] = true;
+			if (h2 == 0) return n.v;
+			frontier.push_back(n);
+			// cout << n.x << " " << n.y << " " << n.v << endl;
+		}
+	}
+	return -1;
+}
+
 int
 main()
 {
 	readInput();
 	cout << part1() << endl;
+	cout << part2() << endl;
 }
-- 
cgit 1.4.1-2-gfad0