aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--src/2022/day24/aoc.cpp50
-rw-r--r--src/2022/day24/aoc.h9
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);