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
114
|
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <map>
#include <queue>
#include <ranges>
#include <set>
#include <sstream>
#include <string>
#include <string_view>
#include <vector>
using namespace std;
class Map {
public:
int N, M, L;
int *cell;
Map(const vector<string>& lines)
: N{(int)lines.size()}, M{(int)lines[0].size()}, cell{new int[M*N]}
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cell[M*i+j] = lines[i][j] == '#' ? -1 : 0;
if (lines[i][j] == 'S') {
is = i;
js = j;
}
if (lines[i][j] == 'E') {
ie = i;
je = j;
}
}
}
findpath();
}
~Map() {
delete[] cell;
}
int& operator()(int i, int j) {
if (i < 0 || i >= N || j < 0 || j >= M)
return out_of_bound;
return cell[M*i+j];
}
const int& operator()(int i, int j) const {
if (i < 0 || i >= N || j < 0 || j >= M)
return out_of_bound;
return cell[M*i+j];
}
int cheats(int x, int y, int k, int p) {
// Cheats <= p starting at x, y saving at least k picoseconds
int count = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
if ((*this)(i, j) != -1)
count += saved(i, j, x, y, p) >= k;
return count;
}
private:
int is, js, ie, je;
int out_of_bound = -1;
vector<pair<int, int>> directions {{0,1}, {0,-1}, {1,0}, {-1,0}};
void findpath() {
int i, j, k;
for (i = is, j = js, k = 1; i != ie || j != je; step(i, j, k))
(*this)(i, j) = k;
(*this)(ie, je) = k;
L = k-1;
}
void step(int& i, int& j, int& k) {
k++;
for (auto p : directions) {
if ((*this)(i+p.first, j+p.second) == 0) {
i = i+p.first;
j = j+p.second;
return;
}
}
cout << "Error! at " << i << ", " << j << endl;
}
int saved(int i, int j, int x, int y, int p) {
if (int d = abs(i-x) + abs(j-y); d > p)
return 0;
else
return abs((*this)(i, j) - (*this)(x, y)) - d;
}
};
int main() {
string line;
vector<string> lines;
while (getline(cin, line))
lines.push_back(line);
Map m(lines);
int count = 0;
for (int i = 0; i < m.N; i++)
for (int j = 0; j < m.M; j++)
if (m(i, j) != -1)
count += m.cheats(i, j, 100, 20);
cout << count / 2 << endl;
return 0;
}
|
