﻿

# Untitled

a guest
Dec 8th, 2019
74
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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. }
RAW Paste Data