2022 day24 part1 dp

1 files changed, 9 insertions, 6 deletions

diff --git a/src/2022/day24/aoc.cpp b/src/2022/day24/aoc.cpp
index eeb3819..373e4ac 100644
--- a/src/2022/day24/aoc.cpp
+++ b/src/2022/day24/aoc.cpp
@@ -16,15 +16,18 @@ bool is_valid(pos p, const std::map<blizzard, int>&m, valley& v) {
   return b && m.find(blizzard{p.x, p.y, '.'}) == m.end() && v.get(p.y, p.x) == '.';
 }
 
-void expedition(int m, pos p, pos target, valley& v, int* min) {
+void expedition(int m, pos p, pos target, valley& v, int* min, bool pass) {
+  if (*min < INT32_MAX && m > *min) return;
   if (p == target) {
     printf("arrived by %d !!!\n", m);
     if (*min > m) *min = m;
   }
   else {
-    if (m < v.get_time(p.y, p.x)) {
-      v.get_time(p.y, p.x) = m;
-      printf("(%d, %d) in %d\n", p.x, p.y, m);
+    auto& t = v.get_time(p.y, p.x);
+
+    if (m < t || pass) {
+      // printf("(%d, %d) in %d, was %d\n", p.x, p.y, m, t);
+      if (!pass) t = m;
 
       v.next();
       std::map<blizzard, int> mp; 
@@ -46,7 +49,7 @@ void expedition(int m, pos p, pos target, valley& v, int* min) {
         auto mv = mv0[i];
         if (is_valid(mv, mp, v)) {
           auto blz = v.blz;
-          expedition(m + 1, mv, target, v, min);
+          expedition(m + 1, mv, target, v, min, i > 2);
           v.blz = blz;
         }
       }
@@ -66,7 +69,7 @@ std::pair<int, int> day24(line_view file) {
 
   int min{INT32_MAX};
   // v.print();
-  expedition(0, {1, 0}, {150, 21}, v, &min);
+  expedition(0, {1, 0}, {150, 21}, v, &min, false);
 
   return {min, 0};
 }