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
|
#include <fstream>
#include <iostream>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
using pos_type = tuple<long, long>;
vector<pos_type>
read_file(string_view filename)
{
fstream input{ filename };
vector<pos_type> data;
long lhs = 0;
long rhs = 0;
char chr = 0;
while ( input >> lhs >> chr >> rhs ) {
data.emplace_back(lhs, rhs);
}
return data;
}
void
part1(const vector<pos_type>& data, long size)
{
set<pos_type> stones{ data.begin(), data.end() };
set<pos_type> seen;
// x, y, distance
queue<tuple<pos_type, long>> queue;
queue.push({ { 0, 0 }, 0 });
while ( !queue.empty() ) {
const auto& [pos, distance] = queue.front();
queue.pop();
const auto [x, y] = pos;
if ( x == size && y == size ) {
cout << distance << endl;
return;
}
if ( x < 0 || y < 0 || x > size || y > size ) {
continue;
}
if ( stones.contains(pos) ) {
continue;
}
if ( seen.contains(pos) ) {
continue;
}
seen.insert(pos);
for ( const auto& [nx, ny]: vector<pos_type>{ { x - 1, y }, { x + 1, y }, { x, y - 1 }, { x, y + 1 } } ) {
queue.push({ { nx, ny }, distance + 1 });
}
}
}
int
main()
{
const auto data = read_file("data/day18.txt");
part1({ data.begin(), data.begin() + 1024 }, 70);
}
|
