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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
#include "common.h"
#include <vector>
namespace aoc2022 {
struct heightmap {
static const int row = 41;
static const int col = 66;
struct pos {
int x;
int y;
friend bool operator==(pos p1, pos p2) {
return p1.x == p2.x && p1.y == p2.y;
}
};
struct height {
char h;
int v = 0;
};
height heights[row * col];
pos start;
pos end;
char& get(pos p) {
return heights[p.y * col + p.x].h;
}
int& was(pos p) {
return heights[p.y * col + p.x].v;
}
bool valid(pos p) {
return p.x >= 0 && p.x < col && p.y >= 0 && p.y < row;
}
void get_next(pos p, pos next[], 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]) && !was(ps[i])) {
bool b1 = get(ps[i]) == get(p) + 1;
bool b2 = get(ps[i]) <= get(p);
if (b1 || b2) {
next[*n] = ps[i];
*n += 1;
}
}
}
}
char * indent (int s) {
static char space[100] = {0};
memset(space, 0 ,100);
for(int i = 0; i < s; i++) {
space[i] = ' ';
}
return space;
};
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 print() {
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
printf("%c", get({j, i}));
}
printf("\n");
}
}
void load(int r, line_view lv) {
const char* p = lv.line;
for (int c = 0; c < col; c++) {
get({c, r}) = *(p + c);
if (*(p + c) == 'S') {
start = pos{c, r};
get({c, r}) = 'a';
}
if (*(p + c) == 'E') {
end = pos{c, r};
get({c, r}) = 'z';
}
// printf("(%d, %d) %c\n", c, r, get({c, r}));
}
}
};
std::pair<int, int> day12(line_view);
}
|
