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
113
|
#include <algorithm>
#include <cstddef>
#include <deque>
#include <iostream>
#include <string>
using namespace std;
static constexpr size_t w = 132, h = 42;
static uint8_t heights[h][w];
struct Point {int x, y, v;};
Point start, goal;
void
readInput()
{
for (auto &r : heights) {
fill(begin(r), end(r), 255);
}
int y = 0;
for (string line; getline(cin, line); ) {
if (h <= y) throw "bad input";
for (int x = 0; x < line.size(); x++) {
if (w <= x) throw "bad input";
char c = line[x];
if (c == 'S') {
start.x = x;
start.y = y;
start.v = 0;
c = 'a';
} else if (c == 'E') {
goal.x = x;
goal.y = y;
goal.v = 0; //unused
c = 'z';
}
heights[y][x] = c - 'a';
}
y++;
}
}
int
part1()
{
bool visited[h][w] = {0};
deque<Point> frontier;
frontier.push_back(start);
while (!frontier.empty()) {
Point p = frontier[0];
frontier.pop_front();
for (auto n : {
Point{p.x + 1, p.y , p.v + 1},
Point{p.x - 1, p.y , p.v + 1},
Point{p.x , p.y + 1, p.v + 1},
Point{p.x , p.y - 1, p.v + 1},
}) {
if (!(0 <= n.x && n.x < w && 0 <= n.y && n.y < h))
continue;
if (visited[n.y][n.x]) continue;
auto h1 = heights[p.y][p.x];
auto h2 = heights[n.y][n.x];
if (h1 + 1 < h2) continue;
visited[n.y][n.x] = true;
if (n.x == goal.x && n.y == goal.y) {
return n.v;
}
frontier.push_back(n);
// cout << n.x << " " << n.y << " " << n.v << endl;
}
}
return -1;
}
int
part2()
{
bool visited[h][w] = {0};
deque<Point> frontier;
frontier.push_back(goal);
while (!frontier.empty()) {
Point p = frontier[0];
frontier.pop_front();
for (auto n : {
Point{p.x + 1, p.y , p.v + 1},
Point{p.x - 1, p.y , p.v + 1},
Point{p.x , p.y + 1, p.v + 1},
Point{p.x , p.y - 1, p.v + 1},
}) {
if (!(0 <= n.x && n.x < w && 0 <= n.y && n.y < h))
continue;
if (visited[n.y][n.x]) continue;
auto h1 = heights[p.y][p.x];
auto h2 = heights[n.y][n.x];
if (h2 + 1 < h1) continue;
visited[n.y][n.x] = true;
if (h2 == 0) return n.v;
frontier.push_back(n);
// cout << n.x << " " << n.y << " " << n.v << endl;
}
}
return -1;
}
int
main()
{
readInput();
cout << part1() << endl;
cout << part2() << endl;
}
|
