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
|
#include "aoc.h"
namespace aoc2022 {
struct pos {
int x;
int y;
bool operator==(pos p) const noexcept {
return x == p.x && y == p.y;
}
};
bool is_valid(pos p, const std::map<blizzard, int>&m, valley& v) {
auto b = p.x >= 0 && p.x < v.width && p.y >= 0 && p.y < v.height;
return b && m.find(blizzard{p.x, p.y, '.'}) == m.end() && v.get(p.y, p.x) == '.';
}
void expedition(int m, pos p, pos target, valley& v, int* min, bool pass) {
if (*min < INT32_MAX && m > *min) return;
if (p == target) {
printf("arrived by %d !!!\n", m);
if (*min > m) *min = m;
}
else {
auto& t = v.get_time(p.y, p.x);
if (m < t || pass) {
// printf("(%d, %d) in %d, was %d\n", p.x, p.y, m, t);
if (!pass) t = m;
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;
}
}
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 < 5; i++) {
auto mv = mv0[i];
if (is_valid(mv, mp, v)) {
auto blz = v.blz;
expedition(m + 1, mv, target, v, min, i > 2);
v.blz = blz;
}
}
}
}
}
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;
});
int min{INT32_MAX};
// v.print();
expedition(0, {1, 0}, {150, 21}, v, &min, false);
return {min, 0};
}
}
|
