-
Notifications
You must be signed in to change notification settings - Fork 9
/
Copy pathday_06b.cpp
97 lines (90 loc) · 2.81 KB
/
day_06b.cpp
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
#include <algorithm>
#include <fstream>
#include <iostream>
#include <ranges>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
struct Point {
Point(const int row = 0, const int col = 0) : row(row), col(col) {}
int row;
int col;
bool operator == (const Point& p) const {
return p.row == row && p.col == col;
}
bool operator < (const Point& p) const {
return p.row < row || (p.row == row && p.col < col);
}
};
struct Hasher {
std::size_t operator () (const Point& p) const {
return p.row;
}
};
const std::vector<Point> moves {
Point(1,0),
Point(0,-1),
Point(-1,0),
Point(0,1),
};
const bool in_map (const Point& p, const std::vector<std::string>& map) {
return !(p.col >= map[0].size() || p.col < 0 || p.row >= map.size() || p.row < 0);
}
bool explore(Point current,
int idx,
std::vector<std::string>& map,
std::unordered_map<Point, std::array<bool, 4>, Hasher> visited_edges,
std::unordered_set<Point, Hasher>& obs,
const bool obstacle_placed) {
while(in_map(current, map)) {
if (!visited_edges.contains(current)) {
visited_edges[current] = {{false, false, false, false}};
}
if (visited_edges[current][idx] && obstacle_placed) {
return true;
}
const auto next = Point(current.row + moves[idx].row, current.col + moves[idx].col);
if (!in_map(next, map)) return false;
if(map[next.row][next.col] == '#') {
idx += 1;
idx %= 4;
} else {
if (!obstacle_placed && !visited_edges.contains(next)) {
const auto c = map[next.row][next.col];
map[next.row][next.col] = '#';
if (explore(current, (idx+1)%4, map, visited_edges, obs, true)) {
obs.insert(next);
}
map[next.row][next.col] = c;
}
visited_edges[current][idx] = true;
current = next;
}
}
return false;
}
int main(int argc, char* argv[]) {
std::string input = "../input/day_06_input";
if (argc > 1) {
input = argv[1];
}
std::ifstream file(input);
std::string line;
std::vector<std::string> map;
Point start;
while(std::getline(file, line)) {
map.push_back(line);
for (const auto [idx, c] : std::views::enumerate(line)) {
if (c == '^') {
start.row = map.size()-1;
start.col = idx;
}
}
}
std::unordered_map<Point, std::array<bool, 4>, Hasher> visited_edges;
std::unordered_set<Point, Hasher> obs;
explore(start, 2, map, visited_edges, obs, false);
std::cout << obs.size() << '\n';
return 0;
}