Advertisement
Valery13

Untitled

Feb 23rd, 2020
107
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.88 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. const int inf = 1e9;
  8.  
  9. struct Points{
  10. int nowX, nowY, value;
  11. };
  12.  
  13. bool checkBorder(int &x, int &y, int &n, int &m){
  14. return (x >= 0 && x < n && y >= 0 && y < m);
  15. }
  16.  
  17. int main(){
  18.  
  19. int n, m;
  20.  
  21. freopen("maze.in", "r", stdin);
  22. freopen("maze.out", "w", stdout);
  23.  
  24. cin >> n >> m;
  25.  
  26. int xStart, yStart, xFinish, yFinish;
  27.  
  28. cin >> xStart >> yStart;
  29. cin >> xFinish >> yFinish;
  30.  
  31. xStart--, yStart--;
  32. xFinish--, yFinish--;
  33.  
  34. // if (xStart == xFinish && yStart == yFinish){
  35. // cout << 0 << endl;
  36. // return 0;
  37. // }
  38.  
  39. int **minimalDistance = new int*[n];
  40. int **room = new int*[n];
  41.  
  42. for (int i = 0; i < n; ++i){
  43. room[i] = new int [m];
  44. minimalDistance[i] = new int [m];
  45. for (int j = 0; j < m; ++j) {
  46. cin >> room[i][j];
  47. room[i][j] ^= 1;
  48. minimalDistance[i][j] = inf;
  49. }
  50. }
  51.  
  52. queue <Points> q;
  53.  
  54. q.push({xStart, yStart, 0});
  55.  
  56. while (!q.empty()){
  57. Points Current = q.front();
  58. q.pop();
  59.  
  60. if (!checkBorder(Current.nowX, Current.nowY, n, m)) continue;
  61.  
  62.  
  63. if (room[Current.nowX][Current.nowY]) continue;
  64.  
  65. if (minimalDistance[Current.nowX][Current.nowY] <= Current.value) continue;
  66.  
  67. minimalDistance[Current.nowX][Current.nowY] = Current.value;
  68.  
  69. for (int delx = -1; delx <= 1; ++delx){
  70. for (int dely = -1; dely <= 1; ++dely) if ((delx == 0 && dely) || (delx && dely == 0)){
  71. q.push({Current.nowX + delx, Current.nowY + dely, Current.value + 1});
  72. }
  73. }
  74. }
  75.  
  76. if (minimalDistance[xFinish][yFinish] == inf){
  77. cout << -1 << endl;
  78. return 0;
  79. }
  80.  
  81. cout << minimalDistance[xFinish][yFinish] << endl;
  82.  
  83. vector <pair <int, int> > ans;
  84.  
  85. while (!(xFinish == xStart && yFinish == yStart)){
  86. ans.push_back({xFinish, yFinish});
  87.  
  88. pair <int, int> to;
  89. int mn = inf;
  90.  
  91. for (int delx = -1; delx <= 1; ++delx){
  92. for (int dely = -1; dely <= 1; ++dely) if ((delx == 0 && dely) || (delx && dely == 0)){
  93. xFinish += delx;
  94. yFinish += dely;
  95. if (checkBorder(xFinish, yFinish, n, m)) {
  96. if (mn > minimalDistance[xFinish][yFinish]){
  97. mn = minimalDistance[xFinish][yFinish];
  98. to = {xFinish, yFinish};
  99. }
  100. }
  101. xFinish -= delx;
  102. yFinish -= dely;
  103. }
  104. }
  105.  
  106.  
  107. xFinish = to.first;
  108. yFinish = to.second;
  109. }
  110.  
  111. ans.push_back({xStart, yStart});
  112.  
  113. for (int i = ans.size() - 1; i >= 0; i--){
  114. cout << ans[i].first + 1 << " " << ans[i].second + 1 << endl;
  115. }
  116.  
  117.  
  118. return 0;
  119. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement