#include using namespace std; void moveUL(int &y1, int &x1) { y1 -= 2; x1--; } void moveUR(int &y1, int &x1) { y1 -= 2; x1++; } void moveR(int &y1, int &x1) { x1 += 2; } void moveLR(int &y1, int &x1) { y1 += 2; x1++; } void moveLL(int &y1, int &x1) { y1 += 2; x1--; } void moveL(int &y1, int &x1) { x1 -= 2; } int selectMove(string &move, int n, int &y1, int &x1, int y2, int x2) { int diffY = y1 - y2; int diffX = x1 - x2; /****************************************************/ /***diffX < 0 destination in right side else left**/ /***diffY > 0 destination is above else down **/ /****************************************************/ if(diffY == 0 && diffX != 0) //only need to go left or right { if(diffX > 0) { //move left moveL(y1,x1); move = "L"; } else { //move right moveR(y1,x1); move = "R"; } } else if(diffY != 0 && diffX == 0) //only vertical moves left { if(diffY > 0) //UL if possible else UR { if(x1 - 1 > 0) //still within N do UL { moveUL(y1,x1); move = "UL"; } else { moveUR(y1,x1); move = "UR"; } } if(diffY < 0) { if(x1 + 1 < n) { moveLR(y1,x1); move = "LR"; } else { moveLL(y1,x1); move = "LL"; } } } else if(diffY != 0 && diffX != 0) //finish vertical moves first { if(diffX > 0 && diffY > 0) //move left and up { moveUL(y1,x1); move = "UL"; } else if(diffX > 0 && diffY <0) //move left and down { moveLL(y1,x1); move = "LL"; } else if(diffX < 0 && diffY > 0) //move right and up { moveUR(y1,x1); move = "UR"; } else if(diffX <0 && diffY < 0) //move right and down { moveLR(y1,x1); move = "LR"; } } return 1; } void printShortestPath(int n, int y1, int x1, int y2, int x2) { if( (y1 - y2) % 2 == 0 ) { int nV = (y1-y2)/2; //number of vertical moves int nH = (x1-x2) - nV; //remainig horizontal moves after vertical if( (nH%2) != 0) { cout<<"Impossible\n"; return; } } else { cout<<"Impossible\n"; return; } string path; int moves = 0; while(!(y1 == y2 && x1 == x2)) { int diffX = x1-x2; int diffY = y1-y2; if(diffY > 0 && diffX == 0) { int nMove = diffY/4; for(int i = 0; i < nMove; i++) { moveUL(y1,x1); if(moves++ != 0) path += " "; path += "UL"; } for(int i = 0; i < nMove; i++) { moveUR(y1,x1); if(moves++ != 0) path += " "; path += "UR"; } } else if(diffY < 0 && diffX == 0) { int nMove = (diffY*(-1))/4; for(int i = 0; i < nMove; i++) { moveLR(y1,x1); if(moves++ != 0) path += " "; path += "LR"; } for(int i = 0; i < nMove; i++) { moveLL(y1,x1); if(moves++ != 0) path += " "; path += "LL"; } } else { string currMove; int possible = selectMove(currMove, n, y1, x1, y2, x2); if(!possible){ cout<<"Impossible"<> 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); }