Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <map>
- #include <cmath>
- #include <queue>
- using namespace std;
- struct Point {
- int x, y;
- friend bool operator <(const Point &p1, const Point &p2) {
- return tie(p1.x, p1.y) < tie(p2.x, p2.y);
- }
- bool operator !=(const Point &p) {
- return x != p.x || y != p.y;
- }
- };
- int main() {
- int cx = 0, cy = 0, x, y, tx, ty;
- cin >> x >> y;
- while (abs(x-cx) > 2 || abs(y-cy) > 2) {
- if (y < cy) {
- if (x >= cx) {
- if (cy - y >= x - cx) {
- cx++;
- cy -= 2;
- }
- else {
- cx += 2;
- cy--;
- }
- }
- else {
- if (cy - y >= cx - x) {
- cx--;
- cy -= 2;
- }
- else {
- cx -= 2;
- cy--;
- }
- }
- }
- else {
- if (x >= cx) {
- if (y - cy >= x - cx) {
- cx++;
- cy += 2;
- }
- else {
- cx += 2;
- cy++;
- }
- }
- else {
- if (y - cy >= cx - x) {
- cx--;
- cy += 2;
- }
- else {
- cx -= 2;
- cy++;
- }
- }
- }
- cout << cx << " " << cy;
- cout << "\n";
- }
- map<Point, bool>used;
- map<Point, Point>pred;
- queue<Point>q;
- q.push({ cx, cy });
- used[{cx, cy}] = true;
- vector<Point>wasd = { {-1, 2}, {-1, -2}, {1, 2}, {1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1} }, path;
- while (!q.empty()) {
- if (q.front().x == x && q.front().y == y) {
- path.push_back({ x, y });
- while (pred[{x, y}] != Point{cx, cy}) {
- path.push_back(pred[{x, y}]);
- tx = pred[{x, y}].x;
- y = pred[{tx, y}].y;
- x = tx;
- }
- break;
- }
- for (auto p : wasd) {
- tx = q.front().x + p.x;
- ty = q.front().y + p.y;
- if (!used[{tx, ty}]) {
- used[{tx, ty}] = true;
- q.push({ tx, ty });
- pred[{tx, ty}] = q.front();
- }
- }
- q.pop();
- }
- reverse(path.begin(), path.end());
- for (auto v : path) {
- cout << v.x << " " << v.y;
- cout << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement