2 files changed, 58 insertions, 2 deletions
diff --git a/src/2022/day12/aoc.cpp b/src/2022/day12/aoc.cpp
index 34913e2..2cebc3c 100644
--- a/src/2022/day12/aoc.cpp
+++ b/src/2022/day12/aoc.cpp
@@ -11,8 +11,14 @@ std::pair<int, int> day12(line_view file) {
       return true;
   });
   hm.flood(hm.start);
+  int a1 = hm.was(hm.end);
 
-  return {hm.was(hm.end), 0};
+  hm.reset();
+  // hm.print();
+  int a2{INT32_MAX};
+  hm.flood_down(hm.end, &a2);
+
+  return {a1, a2};
 }
 
 }
diff --git a/src/2022/day12/aoc.h b/src/2022/day12/aoc.h
index 7d786b4..9fe707e 100644
--- a/src/2022/day12/aoc.h
+++ b/src/2022/day12/aoc.h
@@ -66,6 +66,25 @@ struct heightmap {
     }
   }
 
+  void get_prev(pos p, pos prev[], int* n) {
+    pos ps[] = {
+      {p.x, p.y - 1}, // UP
+      {p.x, p.y + 1}, // DOWN
+      {p.x - 1, p.y}, // LEFT
+      {p.x + 1, p.y}, // RIGHT
+    };
+    for (int i = 0; i < 4; i++) {
+      if (valid(ps[i])) {
+        bool b1 = get(ps[i]) == get(p) - 1;
+        bool b2 = get(ps[i]) >= get(p);
+        if (b1 || b2) {
+          prev[*n] = ps[i];
+          *n += 1;
+        }
+      }
+    }
+  }
+
   void flood(pos p) {
     was(p) = 0;
     std::deque<pos> q = {p};
@@ -85,10 +104,41 @@ struct heightmap {
     }
   }
 
+  void flood_down(pos p, int* nearest) {
+    was(p) = 0;
+    std::deque<pos> q = {p};
+    while (!q.empty()) {
+      pos px = q.front();
+      q.pop_front();
+      if (get(px) == 'a') {
+        *nearest = was(px);
+        return;
+      }
+      pos prev[4];
+      int n{0};
+      get_prev(px, prev, &n);
+      for (int i = 0; i < n; i++) {
+        int x = was(px) + 1;
+        if (x < was(prev[i])) {
+            was(prev[i]) = x;
+            q.push_back(prev[i]);
+        }
+      }
+    }
+  }
+
+  void reset() {
+    for (int i = 0; i < row; i++) {
+      for (int j = 0; j < col; j++) {
+        was({j, i}) = INT32_MAX;
+      }
+    }
+  }
+
   void print() {
     for (int i = 0; i < row; i++) {
       for (int j = 0; j < col; j++) {
-        printf("%c ", get({j, i}));
+        printf("%c", get({j, i}));
       }
       printf("\n");
     }