aboutsummaryrefslogtreecommitdiff
path: root/src/2022/day12/aoc.h
diff options
context:
space:
mode:
authorkaiwu <kaiwu2004@gmail.com>2022-12-13 18:01:35 +0800
committerkaiwu <kaiwu2004@gmail.com>2022-12-13 18:01:35 +0800
commitdfd96e51c36f30a633ca9deb7be51628d85ac056 (patch)
tree589b5588af795b6a191c4d0dcbd846b5eb173134 /src/2022/day12/aoc.h
parentf4a140d4bd7d0a7c2d39c7c266bf2a596f7df49c (diff)
downloadadvent-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.h51
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() {