• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

Kekulidze Jan 21st, 2020 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <queue>
3.
4. using namespace std;
5. struct Position
6. {
7.     int x;
8.     int y;
9. };
10. int n, m;
11. Position  parents[21][21];
12. bool used[21][21];
13. queue<Position> q;
14.
15. bool Check(int x, int y)
16. {
17.     if (x >= 1 && x <= m && y >= 1 && y <= m)
18.         return true;
19.     else return false;
20. }
21. void proc(Position u, int x, int y, int** dist)
22. {
23.     if (Check(x, y) && !used[y][x])
24.     {
25.         used[y][x] = true;
26.         parents[y][x] = u;
27.         dist[y][x] = dist[u.y][u.x] + 1;
28.         Position v = { x,y };
29.         q.push(v);
30.
31.     }
32.
33. }
34. void BFS(Position start, int** dist) {
35.     used[start.y][start.x] = true;
36.     parents[start.y][start.x] = start;
37.     dist[start.y][start.x] = 0;
38.     Position u{ start.x,start.y };
39.     q.push(u);
40.     while (!q.empty()) {
41.         u = q.front();
42.         q.pop();
43.
44.         proc(u, u.x - 1, u.y - 2, dist);
45.         proc(u, u.x - 1, u.y + 2, dist);
46.         proc(u, u.x - 2, u.y - 1, dist);
47.         proc(u, u.x - 2, u.y + 1, dist);
48.         proc(u, u.x + 1, u.y - 2, dist);
49.         proc(u, u.x + 1, u.y + 2, dist);
50.         proc(u, u.x + 2, u.y - 1, dist);
51.         proc(u, u.x + 2, u.y + 1, dist);
52.
53.
54.
55.     }
56. }
57.
58. void print_way(Position u)
59. {
60.     if (parents[u.y][u.x].x != u.x || parents[u.y][u.x].y != u.y)
61.     {
62.         print_way(parents[u.y][u.x]);
63.     }
64.     cout << u.x << ' ' << u.y << endl;
65. }
66. int main()
67. {
68.     freopen("input.txt", "r", stdin);
69.     freopen("output.txt", "w", stdout);
70.
71.
72.     cin >> n >> m;
73.
74.     Position start, end;
75.     int** dist = new int* [21];
76.     for (int i = 1; i <= 21; i++)
77.         dist[i] = new int[21];
78.     cin >> start.x >> start.y;
79.     cin >> end.x >> end.y;
80.     BFS(start, dist);
81.
82.
83.     if (dist[end.y][end.x] > 0)
84.     {
85.         cout << dist[end.y][end.x] << endl;
86.         print_way(end);
87.
88.
89.     }
90.     else if (dist[end.y][end.x] == 0)
91.         cout << 0 << endl << end.x<<" "<<end.y;
92.     else cout <<-1;
93.
94.
95.
96. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Top