-
Notifications
You must be signed in to change notification settings - Fork 0
/
15.cpp
116 lines (102 loc) · 3.71 KB
/
15.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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <iostream>
#include <fstream>
#include <queue>
#include <deque>
#include <vector>
using Cavern = std::vector<std::vector<int>>;
using Point = std::pair<int, int>;
#define SIZE 100
int charToInt(int c) {
return c - '0';
}
Cavern readInput(std::ifstream& in) {
Cavern risks{ SIZE, std::vector<int>(SIZE) };
for (auto&& row: risks) {
for (auto&& col: row) {
col = charToInt(in.get());
}
// skip newline
in.get();
}
return risks;
}
bool isValid(int row, int col, int size) {
return 0 <= row && row < size && 0 <= col && col < size;
}
int heuristics(int row, int col, int size) {
return (size - row) + (size - col);
}
void search(const Cavern& risks, bool astar = false) {
// Dijkstra / A*
auto cmp = [] (const auto& a, const auto& b) { return a.second > b.second; };
std::priority_queue<std::pair<Point, int>,
std::deque<std::pair<Point, int>>,
decltype(cmp)> queue{ cmp };
const int UNDISCOVERED = -1;
Cavern discovered{ risks.size(), std::vector<int>(risks.size(), UNDISCOVERED) };
if (astar) queue.push({{ 0, 0 }, heuristics(0, 0, (int) risks.size()) });
else queue.push({{ 0, 0 }, 0 });
const std::vector<Point> ADJACENT{ std::make_pair(-1, 0),
std::make_pair(0, -1),
std::make_pair(0, 1),
std::make_pair(1, 0) };
int count = 1;
while (!queue.empty() && discovered[discovered.size() - 1][discovered.size() - 1] == UNDISCOVERED) {
auto row = queue.top().first.first;
auto col = queue.top().first.second;
auto len = (astar) ? queue.top().second - heuristics(row, col, (int) risks.size()) : queue.top().second;
if (discovered[row][col] == UNDISCOVERED) {
for (auto&& [i, j]: ADJACENT) {
auto m = row + i;
auto n = col + j;
if (isValid(m, n, (int) risks.size()) && discovered[m][n] == UNDISCOVERED) {
if (astar) queue.push({ { m, n }, len + heuristics(m, n, (int) risks.size()) + risks[m][n] });
else queue.push({ { m, n }, len + risks[m][n] });
++count;
}
}
discovered[row][col] = len;
}
queue.pop();
}
std::cout << ((astar) ? "A*" : "Dijkstra") << std::endl;
std::cout << "Vertices added to queue: " << count << std::endl;
std::cout << "Length of the shortest path: " << discovered[discovered.size() - 1][discovered.size() - 1] << std::endl;
}
int main(int argc, char* argv[]) {
std::ifstream dataFile(argv[1]);
Cavern risks = readInput(dataFile);
dataFile.close();
// partOne
search(risks);
Cavern risksLarge{ risks.size() * 5, std::vector<int>(risks.size() * 5) };
for (int x = 0; x < 5; ++x) {
for (int y = 0; y < 5; ++y) {
for (int i = 0; i < risks.size(); ++i) {
for (int j = 0; j < risks.size(); ++j) {
auto row = x * risks.size() + i;
auto col = y * risks.size() + j;
auto newVal = risks[i][j] + x * 1 + y * 1;
risksLarge[row][col] = (newVal > 9) ? newVal % 10 + 1 : newVal;
}
}
}
}
// partTwo
search(risksLarge);
}
// Dijkstra partOne:
// Vertices added to queue: 19801
// Length of the shortest path: 811
//
// Dijkstra partTwo:
// Vertices added to queue: 499001
// Length of the shortest path: 3012
//
// A* partOne:
// Vertices added to queue: 19799
// Length of the shortest path: 811
//
// A* partTwo:
// Vertices added to queue: 498999
// Length of the shortest path: 3012