Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define all(c) c.begin(),c.end()
- #define rall(c) c.rbegin(),c.rend()
- //#define print(c, type) copy(all(c),ostream_iterator<type>(cout, " "));cout << endl
- #define INF INT_MAX
- using namespace std;
- int to_x, to_y;
- vector<vector<bool> > used(9, vector<bool> (9, false));
- class Cell{
- public:
- int x,y;
- bool operator==(Cell &other){
- return this->x == other.x && this->y == other.y;
- }
- Cell(int x = INF, int y = INF){
- this->x = x;
- this->y = y;
- }
- int dist(Cell &other){
- return max(this->delta_x(other), this->delta_y(other));
- }
- int delta_x(Cell &other){
- return abs(this->x - other.x);
- }
- int delta_y(Cell &other){
- return abs(this->y - other.y);
- }
- vector<Cell> children(){
- vector<Cell> tmp = {
- Cell(this->x+1, this->y+2),
- Cell(this->x+1, this->y-2),
- Cell(this->x-1, this->y+2),
- Cell(this->x-1, this->y-2),
- Cell(this->x+2, this->y+1),
- Cell(this->x+2, this->y-1),
- Cell(this->x-2, this->y+1),
- Cell(this->x-2, this->y-1),
- }, _return;
- for(Cell child: tmp)
- if(child.valid())
- _return.push_back(child);
- return _return;
- }
- void use(){
- used[x + 4 - to_x][y + 4 - to_y] = true;
- }
- bool is_used(){
- return used[x + 4 - to_x][y + 4 - to_y];
- }
- void print(){
- cout << x << " " << y;
- }
- bool valid(){
- return x - to_x >= -4 && x - to_x <= 4 && y - to_y >= -4 && y - to_y <= 4;
- }
- };
- vector<vector<Cell> > p(9, vector<Cell> (9));
- int sign(int expr){
- //if(expr == 0) return 0;
- return (( expr < 0 ) ? -1 : 1);
- }
- void setup(){
- ios::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- }
- int main(){
- setup();
- cin >> to_x >> to_y;
- Cell cur(0,0), to(to_x, to_y);
- while(cur.delta_x(to) > 2 || cur.delta_y(to) > 2 ){
- int signx = sign(to_x - cur.x);
- int signy = sign(to_y - cur.y);
- if(cur.delta_x(to) > cur.delta_y(to)){
- ///x += 2
- ///y += 1
- cur.x+=signx*2;
- cur.y+=signy;
- }
- else {
- cur.x+=signx;
- cur.y+=signy*2;
- }
- cur.print();
- cout << endl;
- }
- ///bfs
- queue<Cell> q;
- q.push(cur);
- cur.use();
- while(!q.empty()){
- Cell cell = q.front();
- q.pop();
- for(Cell child: cell.children()){
- if(child.is_used())
- continue;
- child.use();
- p[child.x + 4 - to_x][child.y + 4 - to_y] = cell;
- q.push(child);
- }
- }
- vector<Cell> order;
- while(!(to == cur)){
- order.push_back(to);
- to = p[to.x + 4 - to_x][to.y + 4 - to_y];
- }
- reverse(all(order));
- for(Cell eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee: order){
- eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee.print();
- cout << endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement