myLoveOnlyForYou

Untitled

May 17th, 2019
117
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.12 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <string>
  4. #include <iomanip>
  5. #include <regex>
  6. #include <cstdlib>
  7.  
  8. using namespace std;
  9.  
  10. int manhattan_distance(int x1, int y1, int x2, int y2) {
  11. return x2 - x1 + y2 - y1;
  12. }
  13.  
  14. struct Point {
  15. int visited, to_watch, dist_from_start, func, parent_x, parent_y;
  16. };
  17.  
  18. struct Coords {
  19. int x, y;
  20. };
  21.  
  22. int main() {
  23. freopen("input.txt", "r", stdin);
  24. freopen("output.txt", "w", stdout);
  25. int n, m; cin >> n >> m;
  26. int x1, x2, y1, y2;
  27. cin >> x1 >> y1 >> x2 >> y2;
  28. x1--; y1--; x2--; y2--;
  29. swap(x1, y1); swap(x2, y2);
  30.  
  31. Point **points = new Point*[n];
  32. int move_x[] = { -1, 0, 1, 0 };
  33. int move_y[] = { 0, 1, 0, -1 };
  34.  
  35. int **matrix = new int*[n];
  36. for (int i = 0; i < n; i++) {
  37. matrix[i] = new int[m];
  38. points[i] = new Point[m];
  39. for (int j = 0; j < m; j++) {
  40. cin >> matrix[i][j];
  41. points[i][j].visited = 0;
  42. points[i][j].to_watch = 0;
  43. points[i][j].dist_from_start = 10000000;
  44. points[i][j].func = 100000000;
  45.  
  46. }
  47. }
  48.  
  49. points[x1][y1].to_watch = 1;
  50. points[x1][y1].parent_x = 0;
  51. points[x1][y1].parent_y = 0;
  52. points[x1][y1].dist_from_start = 0;
  53. points[x1][y1].func = points[x1][y1].dist_from_start + manhattan_distance(x1, y1, x2, y2);
  54.  
  55. while (true) {
  56. bool cond = true;
  57. for (int i = 0; i < n; i++)
  58. for (int j = 0; j < m; j++)
  59. if (points[i][j].to_watch == 0) {
  60. cond = false;
  61. break;
  62. }
  63. if (cond == true)
  64. break;
  65.  
  66. int min_vertex = 10000000000;
  67. int x, y;
  68. for (int i = 0; i < n; i++)
  69. for (int j = 0; j < m; j++)
  70. if (points[i][j].to_watch == 1 && points[i][j].func < min_vertex) {
  71. min_vertex = points[i][j].func;
  72. x = i; y = j;
  73. }
  74. if (x == x2 && y == y2) {
  75. break;
  76. }
  77.  
  78. points[x][y].to_watch = 0;
  79. points[x][y].visited = 1;
  80.  
  81. for (int move = 0; move < 4; move++) {
  82. if (x + move_x[move] < n &&
  83. x + move_x[move] >= 0 &&
  84. y + move_y[move] < m &&
  85. y + move_y[move] >= 0) {
  86.  
  87. int new_x = x + move_x[move],
  88. new_y = y + move_y[move];
  89.  
  90. if (matrix[new_x][new_y] != -1) {
  91. int tentative_score = points[x][y].dist_from_start + 1;
  92.  
  93. if (points[new_x][new_y].visited == 1 && tentative_score >= points[new_x][new_y].dist_from_start)
  94. continue;
  95. if (points[new_x][new_y].visited == 0 || tentative_score < points[new_x][new_y].dist_from_start) {
  96. points[new_x][new_y].parent_x = x; points[new_x][new_y].parent_y = y;
  97. points[new_x][new_y].dist_from_start = tentative_score;
  98. points[new_x][new_y].func = points[new_x][new_y].dist_from_start + manhattan_distance(new_x, new_y, x2, y2);
  99. points[new_x][new_y].to_watch = 1;
  100. }
  101. }
  102. }
  103. }
  104. }
  105. Coords answers[100000];
  106. int x = x2, y = y2;
  107. int answer = 1;
  108. while (x != x1 || y != y1) {
  109. answers[answer].x = x + 1;
  110. answers[answer].y = y + 1;
  111. int new_x = points[x][y].parent_x;
  112. int new_y = points[x][y].parent_y;
  113.  
  114. x = new_x; y = new_y;
  115. answer++;
  116. }
  117. answers[answer].x = x1 + 1;
  118. answers[answer].y = y1 + 1;
  119. cout << answer << endl;;
  120. for (int i = answer; i > 0; i--) {
  121. cout << answers[i].y << " " << answers[i].x << endl;
  122. }
  123. return 0;
  124. }
Advertisement
Add Comment
Please, Sign In to add comment