Advertisement
Guest User

Untitled

a guest
Dec 15th, 2019
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.06 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define all(c) c.begin(),c.end()
  4. #define rall(c) c.rbegin(),c.rend()
  5. //#define print(c, type) copy(all(c),ostream_iterator<type>(cout, " "));cout << endl
  6. #define INF INT_MAX
  7.  
  8. using namespace std;
  9.  
  10.  
  11. int to_x, to_y;
  12.  
  13. vector<vector<bool> > used(9, vector<bool> (9, false));
  14.  
  15. class Cell{
  16. public:
  17.     int x,y;
  18.     bool operator==(Cell &other){
  19.         return this->x == other.x && this->y == other.y;
  20.     }
  21.  
  22.     Cell(int x = INF, int y = INF){
  23.         this->x = x;
  24.         this->y = y;
  25.     }
  26.     int dist(Cell &other){
  27.         return max(this->delta_x(other), this->delta_y(other));
  28.     }
  29.     int delta_x(Cell &other){
  30.         return abs(this->x - other.x);
  31.     }
  32.     int delta_y(Cell &other){
  33.         return abs(this->y - other.y);
  34.     }
  35.     vector<Cell> children(){
  36.         vector<Cell> tmp = {
  37.             Cell(this->x+1, this->y+2),
  38.             Cell(this->x+1, this->y-2),
  39.             Cell(this->x-1, this->y+2),
  40.             Cell(this->x-1, this->y-2),
  41.             Cell(this->x+2, this->y+1),
  42.             Cell(this->x+2, this->y-1),
  43.             Cell(this->x-2, this->y+1),
  44.             Cell(this->x-2, this->y-1),
  45.         }, _return;
  46.  
  47.         for(Cell child: tmp)
  48.             if(child.valid())
  49.                 _return.push_back(child);
  50.  
  51.         return _return;
  52.  
  53.     }
  54.     void use(){
  55.         used[x + 4 - to_x][y + 4 - to_y] = true;
  56.     }
  57.     bool is_used(){
  58.         return used[x + 4 - to_x][y + 4 - to_y];
  59.     }
  60.     void print(){
  61.         cout << x << " " << y;
  62.     }
  63.     bool valid(){
  64.         return x - to_x >= -4 && x - to_x <= 4 && y - to_y >= -4 && y - to_y <= 4;
  65.     }
  66. };
  67.  
  68.  
  69.  
  70. vector<vector<Cell> > p(9, vector<Cell> (9));
  71.  
  72. int sign(int expr){
  73.     //if(expr == 0) return 0;
  74.     return (( expr < 0 ) ? -1 : 1);
  75. }
  76.  
  77. void setup(){
  78.     ios::sync_with_stdio(false);
  79.     cin.tie(0);
  80.     cout.tie(0);
  81. }
  82.  
  83. int main(){
  84.     setup();
  85.     cin >> to_x >> to_y;
  86.     Cell cur(0,0), to(to_x, to_y);
  87.  
  88.     while(cur.delta_x(to) > 2 || cur.delta_y(to) > 2 ){
  89.         int signx = sign(to_x - cur.x);
  90.         int signy = sign(to_y - cur.y);
  91.         if(cur.delta_x(to) > cur.delta_y(to)){
  92.             ///x += 2
  93.             ///y += 1
  94.             cur.x+=signx*2;
  95.             cur.y+=signy;
  96.         }
  97.         else {
  98.             cur.x+=signx;
  99.             cur.y+=signy*2;
  100.         }
  101.         cur.print();
  102.         cout << endl;
  103.     }
  104.     ///bfs
  105.  
  106.     queue<Cell> q;
  107.     q.push(cur);
  108.     cur.use();
  109.  
  110.     while(!q.empty()){
  111.         Cell cell = q.front();
  112.         q.pop();
  113.         for(Cell child: cell.children()){
  114.             if(child.is_used())
  115.                 continue;
  116.             child.use();
  117.             p[child.x + 4 - to_x][child.y + 4 - to_y] = cell;
  118.             q.push(child);
  119.         }
  120.     }
  121.  
  122.     vector<Cell> order;
  123.  
  124.     while(!(to == cur)){
  125.         order.push_back(to);
  126.         to = p[to.x + 4 - to_x][to.y + 4 - to_y];
  127.     }
  128.     reverse(all(order));
  129.  
  130.     for(Cell eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee: order){
  131.         eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee.print();
  132.         cout << endl;
  133.     }
  134.  
  135.  
  136.  
  137. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement