Solution
To start, the parsing code is pretty straight forward
// parse input
freopen("matrix.txt", "r", stdin);
constexpr int SIZE = 80;
long long matrix[SIZE][SIZE];
std::string line;
for (int row = 0; row < SIZE; ++row) {
if (!std::getline(std::cin, line)) {
std::cerr << "Missing row " << row + 1 << '\n';
return 1;
}
std::replace(line.begin(), line.end(), ',', ' ');
std::istringstream input(line);
for (int col = 0; col < SIZE; ++col) {
if (!(input >> matrix[row][col])) {
std::cerr << "Invalid or missing value at row "
<< row + 1 << ", column " << col + 1 << '\n';
return 1;
}
}
}
To find the minimal sum going either right or down is done with dynamic programming. If we’re at cell \((i,j)\), then the best path (minimal sum) is either going to come from one cell up \((i,j-1)\) or one cell to the left \((i-1,j)\) illustrated here:
long long min_sum[SIZE][SIZE];
min_sum[0][0] = matrix[0][0];
for (int i = 1; i < SIZE; i++) {
min_sum[0][i] = matrix[0][i] + min_sum[0][i-1];
min_sum[i][0] = matrix[i][0] + min_sum[i-1][0];
}
for (int i = 1; i < SIZE; i++) {
for (int j = 1; j < SIZE; j++) {
if (min_sum[i-1][j] < min_sum[i][j-1]) {
min_sum[i][j] = matrix[i][j] + min_sum[i-1][j];
} else {
min_sum[i][j] = matrix[i][j] + min_sum[i][j-1];
}
}
}
printf("%lld\n", min_sum[SIZE-1][SIZE-1]); //427337