2022 day24 dp

1 files changed, 18 insertions, 32 deletions

diff --git a/src/2022/day24/aoc.cpp b/src/2022/day24/aoc.cpp
index 21e9d3e..eeb3819 100644
--- a/src/2022/day24/aoc.cpp
+++ b/src/2022/day24/aoc.cpp
@@ -17,54 +17,40 @@ bool is_valid(pos p, const std::map<blizzard, int>&m, valley& v) {
 }
 
 void expedition(int m, pos p, pos target, valley& v, int* min) {
-  if (*min < INT32_MAX && m >= *min) return;
   if (p == target) {
     printf("arrived by %d !!!\n", m);
     if (*min > m) *min = m;
   }
   else {
-    v.next();
-    std::map<blizzard, int> mp; 
-    for (auto& b: v.blz) {
-      auto p = mp.insert({b, 1});
-      if (!p.second) {
-        p.first->second += 1;
-      }
-    }
+    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);
 
-    pos mv0[2] = {
-      {p.x, p.y+1},
-      {p.x+1, p.y},
-    };
-    bool p0{false}, p1{false};
-    for (int i = 0; i < 2; i++) {
-      auto mv = mv0[i];
-      if (is_valid(mv, mp, v)) {
-        p0 = true;
-        auto blz = v.blz;
-        expedition(m + 1, mv, target, v, min);
-        v.blz = blz;
+      v.next();
+      std::map<blizzard, int> mp; 
+      for (auto& b: v.blz) {
+        auto p = mp.insert({b, 1});
+        if (!p.second) {
+          p.first->second += 1;
+        }
       }
-    }
 
-    if (!p0) {
-      pos mv1[2] = {
+      pos mv0[5] = {
+        {p.x, p.y+1},
+        {p.x+1, p.y},
         {p.x, p.y-1},
         {p.x-1, p.y},
+        p,
       };
-      for (int i = 0; i < 2; i++) {
-        auto mv = mv1[i];
+      for (int i = 0; i < 5; i++) {
+        auto mv = mv0[i];
         if (is_valid(mv, mp, v)) {
-          p1 = true;
+          auto blz = v.blz;
           expedition(m + 1, mv, target, v, min);
-          break;
+          v.blz = blz;
         }
       }
     }
-
-    if (!p0 && !p1) {
-      expedition(m + 1, p, target, v, min);
-    }
   }
 }