Advertisement
Guest User

Untitled

a guest
Dec 8th, 2019
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.86 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <algorithm>
  5.  
  6. #define pp pair<int, int>
  7. #define x first
  8. #define y second
  9. #define mp make_pair
  10.  
  11. using namespace std;
  12.  
  13. int main()
  14. {
  15. int N, M, p, q, x1, y1, x2, y2;
  16. cin>>N>>M>>p>>q>>x1>>y1>>x2>>y2;
  17. bool a[N+1][M+1];
  18. pp prev[N+1][M+1];
  19. int d[N+1][M+1];
  20. queue<pp> qu;
  21. pp s=mp(x1, y1);
  22. qu.push (s);
  23. a[s.x][s.y] = true;
  24. prev[s.x][s.y].x = -1;
  25. prev[s.x][s.y].y = -1;
  26. d[s.x][s.y]=0;
  27. while (!qu.empty()) {
  28. pp u = qu.front();
  29. qu.pop();
  30. if(u.x+q>0 && u.x+q<=N && u.y+p>0 && u.y+p<=M){
  31. pp to = mp(u.x+q, u.y+p);
  32. if(!a[to.x][to.y]){
  33. a[to.x][to.y]=true;
  34. qu.push(to);
  35. d[to.x][to.y]=d[u.x][u.y]+1;
  36. prev[to.x][to.y].x=u.x;
  37. prev[to.x][to.y].y=u.y;
  38. }
  39. }
  40. if(u.x+q>0 && u.x+q<=N && u.y-p>0 && u.y-p<=M){
  41. pp to = mp(u.x+q, u.y-p);
  42. if(!a[to.x][to.y]){
  43. a[to.x][to.y]=true;
  44. qu.push(to);
  45. d[to.x][to.y]=d[u.x][u.y]+1;
  46. prev[to.x][to.y].x=u.x;
  47. prev[to.x][to.y].y=u.y;
  48. }
  49. }
  50. if(u.x-q>0 && u.x-q<=N && u.y+p>0 && u.y+p<=M){
  51. pp to = mp(u.x-q, u.y+p);
  52. if(!a[to.x][to.y]){
  53. a[to.x][to.y]=true;
  54. qu.push(to);
  55. d[to.x][to.y]=d[u.x][u.y]+1;
  56. prev[to.x][to.y].x=u.x;
  57. prev[to.x][to.y].y=u.y;
  58. }
  59. }
  60. if(u.x-q>0 && u.x-q<=N && u.y-p>0 && u.y-p<=M){
  61. pp to = mp(u.x-q, u.y-p);
  62. if(!a[to.x][to.y]){
  63. a[to.x][to.y]=true;
  64. qu.push(to);
  65. d[to.x][to.y]=d[u.x][u.y]+1;
  66. prev[to.x][to.y].x=u.x;
  67. prev[to.x][to.y].y=u.y;
  68. }
  69. }
  70. if(u.x+p>0 && u.x+p<=N && u.y+q>0 && u.y+q<=M){
  71. pp to = mp(u.x+p, u.y+q);
  72. if(!a[to.x][to.y]){
  73. a[to.x][to.y]=true;
  74. qu.push(to);
  75. d[to.x][to.y]=d[u.x][u.y]+1;
  76. prev[to.x][to.y].x=u.x;
  77. prev[to.x][to.y].y=u.y;
  78. }
  79. }
  80. if(u.x-p>0 && u.x-p<=N && u.y+q>0 && u.y+q<=M){
  81. pp to = mp(u.x-p, u.y+q);
  82. if(!a[to.x][to.y]){
  83. a[to.x][to.y]=true;
  84. qu.push(to);
  85. d[to.x][to.y]=d[u.x][u.y]+1;
  86. prev[to.x][to.y].x=u.x;
  87. prev[to.x][to.y].y=u.y;
  88. }
  89. }
  90. if(u.x+p>0 && u.x+p<=N && u.y-q>0 && u.y-q<=M){
  91. pp to = mp(u.x+p, u.y-q);
  92. if(!a[to.x][to.y]){
  93. a[to.x][to.y]=true;
  94. qu.push(to);
  95. d[to.x][to.y]=d[u.x][u.y]+1;
  96. prev[to.x][to.y].x=u.x;
  97. prev[to.x][to.y].y=u.y;
  98. }
  99. }
  100. if(u.x-p>0 && u.x-p<=N && u.y-q>0 && u.y-q<=M){
  101. pp to = mp(u.x-p, u.y-q);
  102. if(!a[to.x][to.y]){
  103. a[to.x][to.y]=true;
  104. qu.push(to);
  105. d[to.x][to.y]=d[u.x][u.y]+1;
  106. prev[to.x][to.y].x=u.x;
  107. prev[to.x][to.y].y=u.y;
  108. }
  109. }
  110. }
  111. if(!a[x2][y2]){
  112. cout<<-1<<endl;
  113. return 0;
  114. }else{
  115. int D=d[x2][y2];
  116. cout<<D<<endl;
  117. pp f = mp(x2, y2);
  118. vector<pp> ans;
  119. ans.push_back(f);
  120. while(ans.size()<D+1){
  121. pp last = ans[ans.size()-1];
  122. pp last_new = mp(prev[last.x][last.y].x, prev[last.x][last.y].y);
  123. ans.push_back(last_new);
  124. }
  125. reverse(ans.begin(), ans.end());
  126. for(int i=0; i<=D; i++){
  127. cout<<ans[i].x<<" "<<ans[i].y<<endl;
  128. }
  129. }
  130.  
  131. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement