Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int inf = 1e9;
- const int maxn = 1e3;
- int d[maxn][maxn];
- int dx[8] = {2, 1, -1, -2, -2, -1, 1, 2};
- int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
- bool is_ok(int x, int y) {
- return x >= 0 && y >= 0 && x < maxn && y < maxn;
- }
- struct Point {
- int x, y;
- Point() {}
- Point(int x, int y) : x(x), y(y) {}
- };
- Point pr[maxn][maxn];
- void way(Point p) {
- if (pr[p.x][p.y].x == -1)
- return;
- way(pr[p.x][p.y]);
- cout << p.x << ' ' << p.y << '\n';
- }
- void solve() {
- int x1, y1, x2, y2;
- cin >> x1 >> y1 >> x2 >> y2;
- queue<Point> q;
- q.push({x1, y1});
- d[x1][y1] = 0;
- pr[x1][y1] = {-1, -1};
- while (!q.empty()) {
- Point p = q.front();
- q.pop();
- if (p.x == x2 && p.y == y2)
- break;
- for (int i = 0; i < 8; ++i) {
- int nx = p.x + dx[i];
- int ny = p.y + dy[i];
- if (is_ok(nx, ny) && d[nx][ny] == inf) {
- q.push({nx, ny});
- d[nx][ny] = d[p.x][p.y] + 1;
- pr[nx][ny] = p;
- }
- }
- }
- cout << d[x2][y2] << '\n';
- way({x2, y2});
- }
- signed main() {
- for (int i = 0; i < maxn; ++i) {
- for (int j = 0; j < maxn; ++j) {
- d[i][j] = inf;
- }
- }
- solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement