Advertisement
Guest User

Untitled

a guest
Dec 15th, 2019
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.18 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. int main() {
  5. int Dim1 = 0, Dim2 = 0;
  6. std::cin >> Dim1;
  7. std::cin >> Dim2;
  8.  
  9. using IntMatrix = std::vector<std::vector<int>>;
  10. IntMatrix Field(Dim1, {Dim2, 0});
  11. using CoordsPair = std::pair<int, int>;
  12. CoordsPair Start{0, 0};
  13. for (int i = 0; i < Dim1; ++i) {
  14. for (int j = 0; j < Dim2; ++j) {
  15. std::string Input;
  16. std::cin >> Input;
  17. if (Input[0] == 'S') {
  18. Start = {i, j};
  19. Field[i][j] = 0;
  20. } else
  21. Field[i][j] = std::stoi(Input);
  22. }
  23. }
  24.  
  25. IntMatrix SumField(std::move(Field));
  26. for (int i = Start.first + 1; i < Dim1; ++i) {
  27. SumField[i][Start.second] += SumField[i - 1][Start.second];
  28. }
  29. for (int j = Start.second + 1; j < Dim2; ++j) {
  30. SumField[Start.first][j] += SumField[Start.first][j - 1];
  31. }
  32.  
  33. std::vector<CoordsPair> PathVec;
  34. for (int i = Start.first + 1; i < Dim1; ++i) {
  35. for (int j = Start.second + 1; j < Dim2; ++j) {
  36. CoordsPair Top{i - 1, j}, Left{i, j - 1};
  37. CoordsPair &Biggest =
  38. SumField[Top.first][Top.second] >
  39. SumField[Left.first][Left.second] ? Top : Left;
  40. SumField[i][j] += SumField[Biggest.first][Biggest.second];
  41. }
  42. }
  43.  
  44. CoordsPair PathFindIdx{Dim1 - 1, Dim2 - 1};
  45. bool ReachedTop = false, ReachedLeft = false;
  46. while (!ReachedTop || !ReachedLeft) {
  47. PathVec.emplace_back(PathFindIdx);
  48. if (PathFindIdx.first == Start.first)
  49. ReachedTop = true;
  50. if (PathFindIdx.second == Start.second)
  51. ReachedLeft = true;
  52. CoordsPair UpIdx = {PathFindIdx.first - 1, PathFindIdx.second};
  53. if (ReachedLeft) {
  54. PathFindIdx = UpIdx;
  55. continue;
  56. }
  57. CoordsPair LeftIdx = {PathFindIdx.first, PathFindIdx.second - 1};
  58. if (ReachedTop) {
  59. PathFindIdx = LeftIdx;
  60. continue;
  61. }
  62. bool Upwards =
  63. SumField[UpIdx.first][UpIdx.second] >=
  64. SumField[LeftIdx.first][LeftIdx.second];
  65. PathFindIdx = Upwards ? UpIdx : LeftIdx;
  66. }
  67.  
  68. std::cout << "Path:\n";
  69. for (int i = PathVec.size() - 1; i >= 0; --i) {
  70. std::cout << '(' << PathVec[i].first << "," << PathVec[i].second << ") ";
  71. }
  72. std::cout << "\nCoins: " << SumField[Dim1 - 1][Dim2 - 1] << "\n";
  73. return 0;
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement