1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
|
#include "aoc.h"
#include <deque>
#include <set>
namespace aoc2022 {
struct pos {
int x;
int y;
int t;
friend bool operator<(pos p1, pos p2) {
return p1.x < p2.x ? true : p1.x > p2.x ? false : p1.y < p2.y ? true : p1.y > p2.y ? false : p1.t < p2.t;
}
bool operator==(pos p) const noexcept { return x == p.x && y == p.y; }
};
bool is_valid(pos p, valley& v, std::set<pos>& visited) {
pos px{p.x, p.y, p.t % (v.height * v.width)};
auto pr = visited.insert(px);
if (!pr.second) {
return false;
}
auto blz = v.at(px.t);
auto find = [&blz](blizzard b) -> bool {
for (auto& bx : blz) {
if (bx == b)
return true;
}
return false;
};
auto b = p.x >= 0 && p.x < v.width && p.y >= 0 && p.y < v.height;
return b && !find(blizzard{p.x, p.y, '.'}) && v.get(p.y, p.x) == '.';
}
// bfs
int expedition(pos p, pos target, valley& v, std::set<pos>& visited) {
std::deque<pos> q;
q.push_back(p);
while (!q.empty()) {
auto size = q.size();
while (size-- > 0) {
pos px = q.front();
// printf("(%d,%d) at %d\n", px.x, px.y, px.t);
q.pop_front();
if (px == target) {
return px.t;
}
pos ps[5] = {
{px.x, px.y + 1, px.t + 1}, {px.x + 1, px.y, px.t + 1}, {px.x, px.y - 1, px.t + 1},
{px.x - 1, px.y, px.t + 1}, {px.x, px.y, px.t + 1},
};
for (int i = 0; i < 5; i++) {
if (is_valid(ps[i], v, visited)) {
q.push_back(ps[i]);
}
}
}
}
return INT32_MAX;
}
std::pair<int, int> day24(line_view file) {
// valley v{8,6}; //sample
valley v{152, 22};
int height{0};
per_line(file, [&v, &height](line_view lv) {
v.load(height++, lv);
return true;
});
std::set<pos> visited;
int m1 = expedition({1, 0, 0}, {150, 21, INT32_MAX}, v, visited);
visited.clear();
int m2 = expedition({150, 21, m1}, {1, 0, INT32_MAX}, v, visited);
visited.clear();
int m3 = expedition({1, 0, m2}, {150, 21, INT32_MAX}, v, visited);
// printf("%d %d %d\n", m1, m2, m3);
return {m1, m3};
}
} // namespace aoc2022
|
