#include #include #include #include using namespace std; void move(int* i_curr, int* j_curr, int m){ switch(m){ case 0 : (*j_curr)--; (*i_curr) = (*i_curr) - 2; break; case 1 : (*j_curr)++; (*i_curr) = (*i_curr) - 2; break; case 5 : (*j_curr) = (*j_curr) - 2; break; case 2 : (*j_curr) = (*j_curr) + 2; break; case 4 : (*j_curr)--; (*i_curr) = (*i_curr) + 2; break; case 3 : (*j_curr)++; (*i_curr) = (*i_curr) + 2; break; default : cout << "Well this is bad"; } } int diff(int i_curr, int j_curr,int i_end, int j_end){ int b = abs(i_end-i_curr); int c = abs(j_end-j_curr); return b+c; } string nextMove(int n,int* i_curr, int* j_curr,int i_end, int j_end){ vector moveList = {"UL","UR","R","LR","LL","L"}; int saveI; int saveJ; int diffs, count = 0; int min = 201; int pos = 0; for(string m: moveList){ saveI = *i_curr; saveJ = *j_curr; move(&saveI,&saveJ,count); diffs = diff(saveI,saveJ,i_end,j_end); //cout << "Distance: " << diffs << " "; if(diffs < min && saveI < n && saveJ < n && saveI >= 0 && saveJ >=0){ min = diffs; pos = count; if(diffs == 0){ break; } } count++; } move(i_curr, j_curr,pos); //cout << "Pos: " << pos; return moveList[pos]; } void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { vector instructions; int distance = diff(i_start,j_start,i_end,j_end); int moves = 0, failed = 0; while(distance > 0){ instructions.push_back(nextMove(n,&i_start,&j_start,i_end,j_end)); moves++; //cout << "(" << i_start << ", " << j_start << ")" << endl; distance = diff(i_start,j_start,i_end,j_end); if(distance == 1){ cout << "Impossible"; failed = 1; break; } } if(!failed){ cout << moves << endl; for(string m: instructions){ cout << m << " "; } } // Print the distance along with the sequence of moves. } int main() { int n; cin >> 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; }