D_L3

Максимален път в матрицa

Jan 8th, 2024
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.28 KB | None | 0 0
  1. #include <cmath>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <unordered_map>
  7. #include <climits>
  8. #include <queue>
  9.  
  10. using namespace std;
  11.  
  12. unordered_map<int, vector<int>> graph;
  13.  
  14.  
  15. int findMaxPath(int current, vector<int>& matrix, vector<int>& distances, int finish) {
  16. if (distances[current] != -6000)
  17. return distances[current];
  18. if (current == finish)
  19. return matrix[finish];
  20. int result = INT_MIN;
  21. int curr;
  22. for (auto neighbour : graph[current])
  23. {
  24. curr = findMaxPath(neighbour, matrix, distances, finish);
  25. if (curr > result)
  26. {
  27. result = curr;
  28. }
  29. }
  30. return distances[current] = result + matrix[current];
  31. }
  32.  
  33. int main() {
  34. int n, k, a, b;
  35. cin >> n;
  36. vector<int> matrix(n * n);
  37. vector<int> distances(n * n, -6000);
  38.  
  39. for (int i = 0; i < n * n; i++) {
  40. cin >> matrix[i];
  41. if ((i + 1) % n != 0)
  42. graph[i].push_back(i + 1);
  43. if ((i + n) < n * n)
  44. graph[i].push_back(i + n);
  45. }
  46. cin >> k;
  47. for (int i = 0; i < k; i++) {
  48. cin >> a >> b;
  49. graph[(a - 1) * n + b - 1].push_back(a * n + b);
  50. }
  51.  
  52. cout << findMaxPath(0, matrix, distances, n * n - 1);
  53. }
  54.  
Advertisement
Add Comment
Please, Sign In to add comment