#include using namespace std; int movecount = -1; vector result; class pos{ public: int x; int y; string position; pos(int _x, int _y, string _position):x(_x),y(_y),position(_position){} }; vector posibleMoves(int n, int i_start, int j_start, int i_end, int j_end) { //UL, UR, R, LR, LL, L. vector retval; //UL int x, y; x = i_start - 2; y = j_start - 1; if(x >= 0 && y >= 0 && x < n && y < n && i_end <= i_start && j_end <= j_start && ((j_end < j_start && y > j_end) || j_end == j_start) && ((i_end < i_start && x >= i_end) || i_end == i_start)) retval.push_back(pos(x, y, "UL")); else if(x == i_end && y == j_end){ retval.clear(); retval.push_back(pos(x, y, "UL")); } //UR x = i_start - 2; y = j_start + 1; if(x >= 0 && y >= 0 && x < n && y < n && i_end <= i_start && j_end >= j_start && ((j_end < j_start && y < j_end) || j_end == j_start) && ((i_end < i_start && x >= i_end) || i_end == i_start)) retval.push_back(pos(x, y, "UR")); else if(x == i_end && y == j_end){ retval.clear(); retval.push_back(pos(x, y, "UR")); } //R x = i_start; y = j_start + 2; if(x >= 0 && y >= 0 && x < n && y < n && j_end >= j_start && y < j_end) retval.push_back(pos(x, y, "R")); else if(x == i_end && y == j_end){ retval.clear(); retval.push_back(pos(x, y, "R")); } //LR x = i_start + 2 ; y = j_start + 1; if(x >= 0 && y >= 0 && x < n && y < n && i_end >= i_start && j_end >= j_start && ((j_end > j_start && y < j_end) || j_end == j_start) && ((i_end > i_start && x <= i_end) || i_end == i_start)) retval.push_back(pos(x, y, "LR")); else if(x == i_end && y == j_end){ retval.clear(); retval.push_back(pos(x, y, "LR")); } //LL x = i_start + 2; y = j_start - 1; if(x >= 0 && y >= 0 && x < n && y < n && i_end >= i_start && j_end <= j_start && ((j_end > j_start && y > j_end) || j_end == j_start) && ((i_end < i_start && x <= i_end) || i_end == i_start)) retval.push_back(pos(x, y, "LL")); else if(x == i_end && y == j_end){ retval.clear(); retval.push_back(pos(x, y, "LL")); } //L x = i_start; y = j_start - 2; if(x >= 0 && y >= 0 && x < n && y < n && j_end <= j_start && y > j_end) retval.push_back(pos(x, y, "L")); else if(x == i_end && y == j_end){ retval.clear(); retval.push_back(pos(x, y, "L")); } return retval; } bool next(int n, int i_start, int j_start, int i_end, int j_end, int count) { bool retval = false; vector vec = posibleMoves(n, i_start, j_start, i_end, j_end); if(vec.size() == 0) return false; for(int i = 0; i count ? count : movecount; return true; } else retval = next(n, vec[i].x, vec[i].y, i_end, j_end, count); if(retval){ result.push_back(vec[i].position); return retval; } } return retval; } void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { vector vec = posibleMoves(n, i_start, j_start, i_end, j_end); if(vec.size() == 0) cout<<"Impossible"; bool found = false; for(int i = 0; i =0; i--){ cout<> n; int i_start; int j_start; int i_end; int j_end; cin >> i_start >> j_start >> i_end >> j_end; printShortestPath(n, i_start, j_start, i_end, j_end); return 0; }