Advertisement
Guest User

Untitled

a guest
Dec 8th, 2019
117
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.52 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5. int was[100][100];
  6. int ans = INT_MAX/2, m, n, p, q, x_fin, y_fin;
  7. vector<pair<pair<int,int>,int> > queue;
  8. vector<pair<int,int> > path;
  9. void bfs(int x, int y) {
  10. int a, b, cur;
  11. queue.emplace_back(make_pair(x, y), 0);
  12. was[x][y] = true;
  13. for (int k = 0; k < int(queue.size()); k++) {
  14. a = queue[k].first.first;
  15. b = queue[k].first.second;
  16. cur = queue[k].second;
  17. if (x_fin == a && y_fin == b)
  18. ans = cur;
  19. if (a+p < m && b+q < n && (!was[a+p][b+q])) {
  20. queue.emplace_back(make_pair(a + p, b + q), cur + 1);
  21. was[a + p][b + q] = true;
  22. }
  23. if (a+p < m && b-q >= 0 && (!was[a+p][b-q])) {
  24. queue.emplace_back(make_pair(a + p, b - q), cur + 1);
  25. was[a + p][b - q] = true;
  26. }
  27. if (a-p >= 0 && b+q < n && (!was[a-p][b+q])) {
  28. queue.emplace_back(make_pair(a - p, b + q), cur + 1);
  29. was[a - p][b + q] = true;
  30. }
  31. if (a-p >= 0 && b-q >= 0 && (!was[a-p][b-q])) {
  32. queue.emplace_back(make_pair(a - p, b - q), cur + 1);
  33. was[a - p][b - q] = true;
  34. }
  35. if (a+q < m && b+p < n && (!was[a+q][b+p])) {
  36. queue.emplace_back(make_pair(a + q, b + p), cur + 1);
  37. was[a + q][b + p] = true;
  38. }
  39. if (a+q < m && b-p >= 0 && (!was[a+q][b-p])) {
  40. queue.emplace_back(make_pair(a + q, b - p), cur + 1);
  41. was[a + q][b - p] = true;
  42. }
  43. if (a-q >= 0 && b+p < n && (!was[a-q][b+p])) {
  44. queue.emplace_back(make_pair(a - q, b + p), cur + 1);
  45. was[a - q][b + p] = true;
  46. }
  47. if (a-q >= 0 && b-p >= 0 && (!was[a-q][b-p])) {
  48. queue.emplace_back(make_pair(a - q, b - p), cur + 1);
  49. was[a - q][b - p] = true;
  50. }
  51. }
  52. }
  53. int main() {
  54. int x, y, cur_x, cur_y, cur_ans, i, j;
  55. cin >> m >> n >> p >> q >> x >> y >> x_fin >> y_fin;
  56. x_fin--;
  57. y_fin--;
  58. for (i = 0; i < m; i++)
  59. for (j = 0; j < n; j++)
  60. was[i][j] = false;
  61. bfs(x-1, y-1);
  62. if (ans == INT_MAX/2)
  63. cout << -1;
  64. else {
  65. cout << ans << endl;
  66. for (i = int(queue.size()) - 1; i >= 0; i--)
  67. if (queue[i].first.first == x_fin && queue[i].first.second == y_fin) {
  68. path.emplace_back(x_fin, y_fin);
  69. break;
  70. }
  71. cur_x = x_fin;
  72. cur_y = y_fin;
  73. cur_ans = ans;
  74. for (j = i; j >= 0; j--) {
  75. if (abs(queue[j].first.first - cur_x) == p && abs(queue[j].first.second - cur_y) == q &&
  76. queue[j].second == cur_ans - 1) {
  77. path.emplace_back(queue[j].first.first, queue[j].first.second);
  78. cur_x = queue[j].first.first;
  79. cur_y = queue[j].first.second;
  80. cur_ans = queue[j].second;
  81. } else if (abs(queue[j].first.first - cur_x) == q && abs(queue[j].first.second - cur_y) == p &&
  82. queue[j].second == cur_ans - 1) {
  83. path.emplace_back(queue[j].first.first, queue[j].first.second);
  84. cur_x = queue[j].first.first;
  85. cur_y = queue[j].first.second;
  86. cur_ans = queue[j].second;
  87. }
  88. }
  89. reverse(path.begin(), path.end());
  90. for (i = 0; i < int(path.size()); i++)
  91. cout << path[i].first+1 << " " << path[i].second+1 << endl;
  92. }
  93. return 0;
  94. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement