-
Notifications
You must be signed in to change notification settings - Fork 0
/
day 75
112 lines (94 loc) · 2.65 KB
/
day 75
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
#include <queue>
#include <vector>
#include <iostream>
// 2D matrix: unfortunately x and y are swapped, so we need to write matrix[y][x]
// instead of the more common matrix[x][y]
typedef std::vector<std::vector<unsigned int>> Matrix;
// use a priority queue to find the next cell to process
struct Cell
{
// position
unsigned int x, y;
// sum of shortest route so far
unsigned long long weight;
Cell(unsigned int x_, unsigned int y_, unsigned long long weight_)
: x(x_), y(y_), weight(weight_) {}
// std::priority_queue returns the LARGEST element, therefore I implement this function "the other way 'round"
bool operator<(const Cell& cell) const
{
return weight > cell.weight; // ">" is not a typo !
}
};
// breadth-search
unsigned long long search(const Matrix& matrix)
{
// matrix height/width
const auto size = matrix.size();
// store already processed cells
std::vector<std::vector<bool>> processed(matrix.size());
for (auto& row : processed)
row.resize(matrix.size(), false);
// process cells in increasing distance from starting point
std::priority_queue<Cell> next;
// add starting point (upper left corner)
next.push(Cell(0, 0, matrix[0][0]));
while (!next.empty())
{
// get cell with the smallest weight
Cell cell = next.top();
// and remove it from the queue
next.pop();
// we have been here before ?
// must have been on a shorter route, hence discard current cell
if (processed[cell.y][cell.x])
continue;
processed[cell.y][cell.x] = true;
// finished ?
if (cell.x == size - 1 && cell.y == size - 1)
return cell.weight;
// one step right
if (cell.x + 1 < size)
next.push(Cell(cell.x + 1, cell.y, cell.weight + matrix[cell.y][cell.x + 1]));
// one step down
if (cell.y + 1 < size)
next.push(Cell(cell.x, cell.y + 1, cell.weight + matrix[cell.y + 1][cell.x]));
}
return -1; // failed
}
int main()
{
unsigned int size = 80;
//#define ORIGINAL
#ifndef ORIGINAL
std::cin >> size;
#endif
Matrix matrix(size);
for (auto& row : matrix)
{
row.resize(size);
for (auto& cell : row)
{
#ifdef ORIGINAL
// unfortunately, Project Euler used a CSV format which is a bit tricky to parse in C++
cell = 0;
// read until the number is complete or we run out of input
while (std::cin)
{
char c;
std::cin.get(c);
// number complete ?
if (c < '0' || c > '9')
break;
// add digit to current number
cell *= 10;
cell += c - '0';
}
#else
std::cin >> cell;
#endif
}
}
// go !
std::cout << search(matrix) << std::endl;
return 0;
}