diff options
| -rw-r--r-- | src/2022/day12/aoc.cpp | 13 | ||||
| -rw-r--r-- | src/2022/day12/aoc.h | 34 |
2 files changed, 41 insertions, 6 deletions
diff --git a/src/2022/day12/aoc.cpp b/src/2022/day12/aoc.cpp index c0d1db5..7b79e94 100644 --- a/src/2022/day12/aoc.cpp +++ b/src/2022/day12/aoc.cpp @@ -11,13 +11,14 @@ std::pair<int, int> day12(line_view file) { return true; }); - hm.print(); - std::vector<int> paths; - hm.was(hm.start) += 1; - hm.find(0, hm.start, paths); + // hm.print(); + std::vector<heightmap::pos> ps; + hm.find_prev(0, hm.end, ps); - std::sort(paths.begin(), paths.end()); - return {paths[0], 0}; + for (auto &p : ps) { + printf("%d %d\n", p.x, p.y); + } + return {0, 0}; } } diff --git a/src/2022/day12/aoc.h b/src/2022/day12/aoc.h index a771bfc..3ac0c76 100644 --- a/src/2022/day12/aoc.h +++ b/src/2022/day12/aoc.h @@ -56,6 +56,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; + } + } + } + } + char * indent (int s) { static char space[100] = {0}; memset(space, 0 ,100); @@ -65,6 +84,21 @@ struct heightmap { return space; }; + void find_prev(int steps, pos p, std::vector<pos>& as) { + // printf("%s (%d,%d) %c\n", indent(steps), p.x, p.y, get(p)); + if (get(p) == 'a') { + as.push_back(p); + } + else { + pos prev[4]; + int n = 0; + get_prev(p, prev, &n); + for (int i = 0; i < n; i++) { + find_prev(steps + 1, prev[i], as); + } + } + } + void find(int steps, pos p, std::vector<int>& paths) { // printf("%s (%d,%d) %c\n", indent(steps), p.x, p.y, get(p)); if (p == end) { |