#include #include #include using namespace std; int n_moves = 0; string moves; //priority = UL, UR, R, LR, LL, L bool IsEndpointsValid(int n, int i_start, int j_start, int i_end, int j_end); vector UL(int i, int j); vector UR(int i, int j); vector R(int i, int j); vector LR(int i, int j); vector LL(int i, int j); vector L(int i, int j); bool IsEndpointsValid(int n, int i_start, int j_start, int i_end, int j_end){ if((abs(i_start - i_end))%4 == 0 && (abs(j_start - j_end))%2 == 0) return true; else if((abs(i_start - i_end))%2 == 0 && (abs(j_start - j_end))%2 == 1) return true; else return false; } vector UL(int i, int j){ vector v = {i-2, j-1}; return v; } vector UR(int i, int j){ vector v = {i-2, j+1}; return v; } vector R(int i, int j){ vector v = {i, j+2}; return v; } vector LL(int i, int j){ vector v = {i+2, j-1}; return v; } vector LR(int i, int j){ vector v = {i+2, j+1}; return v; } vector L(int i, int j){ vector v = {i, j-2}; return v; } void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { // Print the distance along with the sequence of moves. vector current_position = {i_start, j_start}; if(!IsEndpointsValid(n, i_start, j_start, i_end, j_end)){ cout<<"Impossible"; return; } //cout << current_position[0] <<" "<< current_position[1] << endl; if(current_position[0] == i_end && current_position[1] == j_end){ cout<< n_moves< i_end){ if(current_position[1] >= j_end){ n_moves++; moves.append("UL "); current_position = UL(current_position[0], current_position[1]); printShortestPath(n,current_position[0], current_position[1], i_end, j_end); } else if(current_position[1] < j_end){ n_moves++; moves.append("UR "); current_position = UR(current_position[0], current_position[1]); printShortestPath(n,current_position[0], current_position[1], i_end, j_end); } } else if(current_position[0] < i_end){ if(current_position[1] <= j_end){ n_moves++; moves.append("LR "); current_position = LR(current_position[0], current_position[1]); printShortestPath(n,current_position[0], current_position[1], i_end, j_end); } else if(current_position[1] > j_end){ n_moves++; moves.append("LL "); current_position = LL(current_position[0], current_position[1]); printShortestPath(n,current_position[0], current_position[1], i_end, j_end); } } else { if(current_position[1] > j_end){ n_moves++; moves.append("L "); current_position = L(current_position[0], current_position[1]); printShortestPath(n,current_position[0], current_position[1], i_end, j_end); } if(current_position[1] < j_end){ n_moves++; moves.append("R "); current_position = R(current_position[0], current_position[1]); printShortestPath(n,current_position[0], current_position[1], i_end, j_end); } } } 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; }