diff options
author | kaiwu <kaiwu2004@gmail.com> | 2022-12-13 18:01:35 +0800 |
---|---|---|
committer | kaiwu <kaiwu2004@gmail.com> | 2022-12-13 18:01:35 +0800 |
commit | dfd96e51c36f30a633ca9deb7be51628d85ac056 (patch) | |
tree | 589b5588af795b6a191c4d0dcbd846b5eb173134 /src/2022/day12/aoc.h | |
parent | f4a140d4bd7d0a7c2d39c7c266bf2a596f7df49c (diff) | |
download | advent-of-code-dfd96e51c36f30a633ca9deb7be51628d85ac056.tar.gz advent-of-code-dfd96e51c36f30a633ca9deb7be51628d85ac056.zip |
2022 day12 bfs
Diffstat (limited to 'src/2022/day12/aoc.h')
-rw-r--r-- | src/2022/day12/aoc.h | 51 |
1 files changed, 21 insertions, 30 deletions
diff --git a/src/2022/day12/aoc.h b/src/2022/day12/aoc.h index 3ac0c76..a7380b2 100644 --- a/src/2022/day12/aoc.h +++ b/src/2022/day12/aoc.h @@ -1,5 +1,6 @@ #include "common.h" #include <vector> +#include <deque> namespace aoc2022 { @@ -84,36 +85,26 @@ 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) { - paths.push_back(steps); - } - else { - pos next[4]; - int n = 0; - get_next(p, next, &n); - for(int i = 0; i < n; i++) { - was(next[i]) += 1; - find(steps + 1, next[i], paths); - was(next[i]) -= 1; - } - } + void find(pos p, std::vector<int>& paths) { + std::deque<pos> q = {p}; + int steps{0}; + while (!q.empty()) { + steps += 1; + pos px = q.front(); + q.pop_front(); + was(px) += 1; + pos ps[4]; + int n{0}; + get_prev(px, ps, &n); + for (int i = 0; i < n; i++) { + if (ps[i] == start) { + paths.push_back(steps); + } + else { + q.push_back(ps[i]); + } + } + } } void print() { |