Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- int main() {
- int Dim1 = 0, Dim2 = 0;
- std::cin >> Dim1;
- std::cin >> Dim2;
- using IntMatrix = std::vector<std::vector<int>>;
- IntMatrix Field(Dim1, {Dim2, 0});
- using CoordsPair = std::pair<int, int>;
- CoordsPair Start{0, 0};
- for (int i = 0; i < Dim1; ++i) {
- for (int j = 0; j < Dim2; ++j) {
- std::string Input;
- std::cin >> Input;
- if (Input[0] == 'S') {
- Start = {i, j};
- Field[i][j] = 0;
- } else
- Field[i][j] = std::stoi(Input);
- }
- }
- IntMatrix SumField(std::move(Field));
- for (int i = Start.first + 1; i < Dim1; ++i) {
- SumField[i][Start.second] += SumField[i - 1][Start.second];
- }
- for (int j = Start.second + 1; j < Dim2; ++j) {
- SumField[Start.first][j] += SumField[Start.first][j - 1];
- }
- std::vector<CoordsPair> PathVec;
- for (int i = Start.first + 1; i < Dim1; ++i) {
- for (int j = Start.second + 1; j < Dim2; ++j) {
- CoordsPair Top{i - 1, j}, Left{i, j - 1};
- CoordsPair &Biggest =
- SumField[Top.first][Top.second] >
- SumField[Left.first][Left.second] ? Top : Left;
- SumField[i][j] += SumField[Biggest.first][Biggest.second];
- }
- }
- CoordsPair PathFindIdx{Dim1 - 1, Dim2 - 1};
- bool ReachedTop = false, ReachedLeft = false;
- while (!ReachedTop || !ReachedLeft) {
- PathVec.emplace_back(PathFindIdx);
- if (PathFindIdx.first == Start.first)
- ReachedTop = true;
- if (PathFindIdx.second == Start.second)
- ReachedLeft = true;
- CoordsPair UpIdx = {PathFindIdx.first - 1, PathFindIdx.second};
- if (ReachedLeft) {
- PathFindIdx = UpIdx;
- continue;
- }
- CoordsPair LeftIdx = {PathFindIdx.first, PathFindIdx.second - 1};
- if (ReachedTop) {
- PathFindIdx = LeftIdx;
- continue;
- }
- bool Upwards =
- SumField[UpIdx.first][UpIdx.second] >=
- SumField[LeftIdx.first][LeftIdx.second];
- PathFindIdx = Upwards ? UpIdx : LeftIdx;
- }
- std::cout << "Path:\n";
- for (int i = PathVec.size() - 1; i >= 0; --i) {
- std::cout << '(' << PathVec[i].first << "," << PathVec[i].second << ") ";
- }
- std::cout << "\nCoins: " << SumField[Dim1 - 1][Dim2 - 1] << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement