Advertisement
deushiro

Untitled

Dec 15th, 2019
176
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.67 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <queue>
  6. #include <map>
  7. #include <set>
  8. #include <bitset>
  9.        
  10. using namespace std;
  11.  
  12. typedef long long ll;
  13.  
  14. struct bf{
  15.     int v, u, c;
  16. };
  17.  
  18. int main() {
  19.     int a, b, v, u, c;
  20.     cin >> a >> b;
  21.     int rx = a;
  22.     int ry = b;
  23.     map<pair<int, int>, int> m;
  24.     queue<bf> q;
  25.     q.push({0, 0, 0});
  26.     vector<pair<int, int>> move = {{-1, 2}, {-1, -2}, {1, 2}, {1, -2},{2, -1}, {2, 1}, {-2, -1}, {-2, 1}};
  27.     while(v != a || u != b){
  28.         v = q.front().v;
  29.         u = q.front().u;
  30.         c = q.front().c;
  31.         q.pop();
  32.         for(int i = 0; i < 8; ++i){
  33.             if(!m.count({v + move[i].first, u + move[i].second}) && v + move[i].first - a - (v - a) < 2 /*&& u + move[i].second - b - (u - b) < 2*/){
  34.                 m[{v + move[i].first, u + move[i].second}] = c + 1;
  35.                 q.push({v + move[i].first, u + move[i].second, c + 1});
  36.             }
  37.         }
  38.     }
  39.     c = 1e9;
  40.     vector<pair<int, int>> ans;
  41.     while(a != 0 || b != 0){
  42.         int x = 0;
  43.         int y = 0;
  44.         for(int i = 0; i < 8; ++i){
  45.             if(m[{a + move[i].first, b + move[i].second}] > 0 && m[{a + move[i].first, b + move[i].second}] < c){
  46.                 x = a + move[i].first;
  47.                 y = b + move[i].second;
  48.                 c = m[{a + move[i].first, b + move[i].second}];
  49.             }
  50.         }
  51.         a = x;
  52.         b = y;
  53.         ans.push_back({a, b});
  54.     }
  55.     for(int i = 1; i < ans.size(); ++i){
  56.         cout << ans[ans.size() - i - 1].first << " " << ans[ans.size() - i - 1].second << "\n";
  57.     }
  58.     cout << rx << " " << ry << "\n";
  59. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement