#include #define MAXN 202 using namespace std; struct e{ string ch; e *parent; bool seen; int i,j; e() : ch(""), parent(NULL), seen(false), i(0), j(0){} void move(e *p, string choice){ seen = true; ch = choice; parent = p; } }; int N; e* yol[MAXN][MAXN]; inline bool legit(int i, int j){ return i>=0 and j>=0 and iseen == false; } vector solve(int is, int js, int ie, int je){ // init yol for(int i=0 ; ii = i; yol[i][j]->j = j; } } // RIGHT ORDER : UL, UR, R, LR, LL, L queue Q; // push n mark n start bfs Q.push(yol[is][js]); yol[is][js]->seen = true; while(Q.size()){ e *current = Q.front(); Q.pop(); int i = current->i; int j = current->j; // upper left if(legit(i-2, j-1)){ yol[i-2][j-1]->move(current, "UL"); Q.push(yol[i-2][j-1]); } // upper right if(legit(i-2, j+1)){ yol[i-2][j+1]->move(current, "UR"); Q.push(yol[i-2][j+1]); } // right if(legit(i, j+2)){ yol[i][j+2]->move(current, "R"); Q.push(yol[i][j+2]); } // lower right if(legit(i+2, j+1)){ yol[i+2][j+1]->move(current, "LR"); Q.push(yol[i+2][j+1]); } // lower left if(legit(i+2, j-1)){ yol[i+2][j-1]->move(current, "LL"); Q.push(yol[i+2][j-1]); } // left if(legit(i, j-2)){ yol[i][j-2]->move(current, "L"); Q.push(yol[i][j-2]); } } vector res; e *step = yol[ie][je]; while(step->parent){ res.push_back(step->ch); step = step->parent; } return res; } void printShortestPath(int is, int js, int ie, int je) { int idiff = abs(is - ie); int jdiff = abs(js - je); if( (idiff%2) or ((idiff>>1)%2 != jdiff%2)){ cout << "Impossible" << endl; return; } // res is reversed. vector res =solve(is, js, ie, je); reverse(res.begin(), res.end()); int res_size = res.size(); cout << res_size << endl << res[0]; for(int i=1 ; i> N; int i_start, j_start; int i_end, j_end; cin >> i_start >> j_start >> i_end >> j_end; printShortestPath(i_start, j_start, i_end, j_end); return 0; } /* // RIGHT ORDER : UL, UR, R, LR, LL, L // returns the reverse path. vector solve(int is, int js, int ie, int je){ // base if(is == ie and js == je) return vector(); vector res; // upper left if(ie < is and je <= js){ res = solve(is-2, js-1, ie, je); res.push_back("UL"); } // upper right else if(ie < is){ res = solve(is-2, js+1, ie, je); res.push_back("UR"); } // right else if(je - js > (ie - is)/2 ){ res = solve(is, js+2, ie, je); res.push_back("R"); } // lower right else if(ie > is and je>=js){ res = solve(is+2, js+1, ie, je); res.push_back("LR"); } // lower left else if(ie > is ){ res = solve(is+2, js-1, ie, je); res.push_back("LL"); } // left else { res = solve(is, js-2, ie, je); res.push_back("L"); } return res; }*/