Advertisement
Gosunov

Untitled

Mar 10th, 2022
142
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.34 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int inf = 1e9;
  6.  
  7. const int maxn = 1e3;
  8. int d[maxn][maxn];
  9.  
  10. int dx[8] = {2, 1, -1, -2, -2, -1, 1, 2};
  11. int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
  12.  
  13. bool is_ok(int x, int y) {
  14.     return x >= 0 && y >= 0 && x < maxn && y < maxn;
  15. }
  16.  
  17. struct Point {
  18.     int x, y;
  19.     Point() {}
  20.     Point(int x, int y) : x(x), y(y) {}
  21. };
  22.  
  23. Point pr[maxn][maxn];
  24.  
  25. void way(Point p) {
  26.     if (pr[p.x][p.y].x == -1)
  27.         return;
  28.     way(pr[p.x][p.y]);
  29.     cout << p.x << ' ' << p.y << '\n';
  30. }
  31.  
  32. void solve() {
  33.     int x1, y1, x2, y2;
  34.     cin >> x1 >> y1 >> x2 >> y2;
  35.     queue<Point> q;
  36.     q.push({x1, y1});
  37.     d[x1][y1] = 0;
  38.     pr[x1][y1] = {-1, -1};
  39.     while (!q.empty()) {
  40.         Point p = q.front();
  41.         q.pop();
  42.         if (p.x == x2 && p.y == y2)
  43.             break;
  44.         for (int i = 0; i < 8; ++i) {
  45.             int nx = p.x + dx[i];
  46.             int ny = p.y + dy[i];
  47.             if (is_ok(nx, ny) && d[nx][ny] == inf) {
  48.                 q.push({nx, ny});
  49.                 d[nx][ny] = d[p.x][p.y] + 1;
  50.                 pr[nx][ny] = p;
  51.             }
  52.         }
  53.     }
  54.     cout << d[x2][y2] << '\n';
  55.     way({x2, y2});
  56. }
  57.  
  58. signed main() {
  59.     for (int i = 0; i < maxn; ++i) {
  60.         for (int j = 0; j < maxn; ++j) {
  61.             d[i][j] = inf;
  62.         }
  63.     }
  64.     solve();
  65. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement