Advertisement
Guest User

Untitled

a guest
Dec 15th, 2019
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.82 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. typedef long long ll;
  4.  
  5. using namespace std;
  6.  
  7. int a, b;
  8.  
  9. int main() {
  10.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  11.     cin >> a >> b;
  12.     vector<pair<int, int>> res = {{a, b}};
  13.     while (a != 0 && abs(a) >= 5 && abs(b) >= 5){
  14.         if (a < 0){
  15.             if (a == -1){
  16.                 if (b > 0){
  17.                     a++;
  18.                     b-=2;
  19.                 }
  20.                 else{
  21.                     a++;
  22.                     b += 2;
  23.                 }
  24.             }
  25.             else{
  26.                 if (b > 0){
  27.                     a+= 2;
  28.                     b--;
  29.                 }
  30.                 else{
  31.                     a += 2;
  32.                     b++;
  33.                 }
  34.             }
  35.         }
  36.         else{
  37.             if(a == 1){
  38.                 if (b > 0){
  39.                     a--;
  40.                     b -= 2;
  41.                 }
  42.                 else{
  43.                     a--;
  44.                     b += 2;
  45.                 }
  46.             }
  47.             else{
  48.                 if (b > 0){
  49.                     a -= 2;
  50.                     b--;
  51.                 }
  52.                 else{
  53.                     a -= 2;
  54.                     b++;
  55.                 }
  56.             }
  57.         }
  58.         res.emplace_back(a, b);
  59.     }
  60.     while (b != 0 && abs(a) >= 5 && abs(b) >= 5){
  61.         if (b > 0){
  62.             if (b == 1){
  63.                 if (a > 0){
  64.                     a -= 2;
  65.                     b--;
  66.                 }
  67.                 else {
  68.                     a += 2;
  69.                     b--;
  70.                 }
  71.             }
  72.             else {
  73.                 if (a > 0){
  74.                     a--;
  75.                     b-= 2;
  76.                 }
  77.                 else {
  78.                     a++;
  79.                     b -= 2;
  80.                 }
  81.             }
  82.         }
  83.         else{
  84.             if (b == -1){
  85.                 if (a > 0){
  86.                     a -= 2;
  87.                     b++;
  88.                 }
  89.                 else{
  90.                     a += 2;
  91.                     b++;
  92.                 }
  93.             }
  94.             else{
  95.                 if (a > 0){
  96.                     a--;
  97.                     b += 2;
  98.                 }
  99.                 else {
  100.                     a++;
  101.                     b+= 2;
  102.                 }
  103.             }
  104.         }
  105.         res.emplace_back(a, b);
  106.     }
  107.     const int A = 8;
  108.     a += A; b += A;
  109.     vector<vector<int>> d(2*A, vector<int>(2*A, INT_MAX));
  110.     vector<vector<pair<int, int>>> path(2*A, vector<pair<int, int>>(2*A, {-1, -1}));
  111.     queue<pair<int, int>> q;
  112.     vector<pair<int, int>> moves = {{2, 1}, {2, -1}, {1, 2}, {1, -2}, {-2, 1}, {-2, -1}, {-1, 2}, {-1, -2}};
  113.     d[a][b] = 0;
  114.     q.push({a, b});
  115.     while (!q.empty() && d[A][A] == INT_MAX){
  116.         pair<int, int> p = q.back();
  117.         q.pop();
  118.         for (pair<int, int> &t1 : moves){
  119.             pair<int, int> m = {p.first+t1.first, p.second + t1.second};
  120.             if (m.first >= 0 && m.first < 2*A && m.second >= 0 && m.second < 2*A){
  121.                 if (d[m.first][m.second] > d[p.first][p.second] + 1){
  122.                     d[m.first][m.second] = d[p.first][p.second] + 1;
  123.                     path[m.first][m.second] = p;
  124.                     q.push(m);
  125.                 }
  126.             }
  127.         }
  128.     }
  129.     vector<pair<int, int>> tmp;
  130.     pair<int, int> p = {A, A};
  131.     while (path[p.first][p.second] != make_pair(-1, -1)){
  132.         tmp.emplace_back(p.first - A, p.second-A);
  133.         p = path[p.first][p.second];
  134.     }
  135.     reverse(tmp.begin(), tmp.end());
  136.     for (int i = 0; i < tmp.size(); ++i){
  137.         res.emplace_back(tmp[i].first, tmp[i].second);
  138.     }
  139.     reverse(res.begin(), res.end());
  140.     for (int i = 1; i < res.size(); ++i){
  141.         cout << res[i].first << ' ' << res[i].second << '\n';
  142.     }
  143.  
  144.     return 0;
  145. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement