day 12 part 2

1 files changed, 32 insertions, 0 deletions

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
@@ -74,8 +74,40 @@ part1()
 }
 
 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;
 }