diff options
-rw-r--r-- | src/2022/day24/aoc.cpp | 50 | ||||
-rw-r--r-- | src/2022/day24/aoc.h | 9 |
2 files changed, 27 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); - } } } diff --git a/src/2022/day24/aoc.h b/src/2022/day24/aoc.h index 455079f..5102256 100644 --- a/src/2022/day24/aoc.h +++ b/src/2022/day24/aoc.h @@ -33,16 +33,25 @@ struct valley { int height; char* pixel; + int* dp; std::vector<blizzard> blz; valley(int w, int h): width(w), height(h) { pixel = (char*) malloc(width * height); + dp = (int*) malloc(width * height * sizeof(int)); + for(int i = 0; i < width * height; i++) { + *(dp + i) = INT32_MAX; + } } char& get(int h, int w) { return *(pixel + h*width + w); } + int& get_time(int h, int w) { + return *(dp + h*width + w); + } + void load(int h, line_view lv) { for(size_t i = 0; i < lv.length - 1; i++) { char c = *(lv.line + i); |