#include #include #include #include #include using namespace std; //UL, UR, R, LR, LL, L bool myComp(string lhs, string rhs){ if (lhs == "UL") return true; if (rhs == "UL") return false; if (lhs == "UR") return true; if (rhs == "UR") return false; if (lhs == "R") return true; if (rhs == "R") return false; if (lhs == "LR") return true; if (rhs == "LR") return false; if (lhs == "LL") return true; if (rhs == "LL") return false; return true; } void printMoves(vector moves){ sort(moves.begin(), moves.end(), myComp); cout << moves.size() << endl; for (auto i:moves){ cout << i << " "; } cout << endl; } int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ //Determine the number of up or down moves necessary --> double num = (double)(|j_end - j_start|)/2.0 //if this is not equal to the integer version, it's not possible i.e. num == (int)num; //determine how many lefts or rights are needed: int numl = j_end - j_start; //use as many of the up/down moves to eat these up: //1) numl == num --> just print out num UL's/DL's or UR's/DR's //2) numl > num --> //a) if (numl - num) % 2 == 0 --> print (numl - num) / 2 UL's/DL's or UR's/DR's then the opposite //b) else: print num - 1 of those, then print the last one the opposite direction (further away), then use a R or L //3) numl < num --> //a) //print numl UL's/DL's/UR's/DR's //if (num - numl) % 2 == 0, print (num - numl) / 2 UL's/etc. then the same of the opposite L/R direction //else: print int n; cin >> n; int i_start, j_start, i_end, j_end; cin >> j_start >> i_start >> j_end >> i_end; //I swapped these because I was thinking backwards and it's easier for me this way //If the number of jumps up/down is odd, we can't reach it (can only go up/down by 2's) if (abs(j_end - j_start) % 2 == 1) { cout << "Impossible" << endl; return 0; } vector moves; //Number of "moves" up or down: int num_ud = abs(j_end - j_start) / 2; //number of "moves" left or right: int num_lr = abs(i_end - i_start); string print_ud = ""; //Create the necessary strings: if (j_start < j_end){ print_ud.push_back('L'); } else if (j_start > j_end) { print_ud.push_back('U'); } if (i_start < i_end){ print_ud.push_back('R'); } else { print_ud.push_back('L'); } string print_lr = "L"; if (i_start < i_end) { print_lr = "R"; } //When all of the left/right moves can be done with the same up or down move: if (num_lr == num_ud){ //Create the string to print: string move_to_print = ""; if (j_start < j_end) { move_to_print.push_back('L'); } else if (j_start > j_end) { move_to_print.push_back('U'); } if (i_start < i_end) { move_to_print.push_back('R'); } else if (i_start > i_end) { move_to_print.push_back('L'); } //Print the moves: for (int i = 0; i < num_lr; ++i){ moves.push_back(move_to_print); } } else if (num_lr > num_ud){ //Print all of the up's/downs: for (int i = 0; i < num_ud - 1; ++i){ moves.push_back(print_ud); } if ((num_lr - num_ud) % 2 == 0){ moves.push_back(print_ud); //Print the UL's/DL's/etc. for (int i = 0; i < (num_lr - num_ud) / 2; ++i){ moves.push_back(print_lr); } } else{ print_ud = ""; //Create the necessary strings: if (j_start < j_end){ print_ud.push_back('L'); } else if (j_start > j_end) { print_ud.push_back('U'); } if (i_start < i_end){ print_ud.push_back('L'); } else { print_ud.push_back('R'); } moves.push_back(print_ud); //Print L/R's for (int i = 0; i < (num_lr - num_ud + 1) / 2; ++i){ moves.push_back(print_lr); } } } else{ //If numUD > numLR //3) numl < num --> //a) //print numl UL's/DL's/UR's/DR's //if (num - numl) % 2 == 0, print (num - numl) / 2 UL's/etc. then the same of the opposite L/R direction //else: print if ((num_ud - num_lr) % 2 != 0){ cout << "Impossible" << endl; return 0; } //We'll need to print these at some point, so do it at the beginning: for (int i = 0; i < num_lr; ++i){ moves.push_back(print_ud); } for (int i = 0; i < (num_ud - num_lr) / 2; ++i){ moves.push_back(print_ud); } print_ud = ""; //Create the necessary strings: if (j_start < j_end){ print_ud.push_back('L'); } else if (j_start > j_end) { print_ud.push_back('U'); } if (i_start < i_end){ print_ud.push_back('L'); } else { print_ud.push_back('R'); } for (int i = 0; i < (num_ud - num_lr) / 2; ++i){ moves.push_back(print_ud); } } printMoves(moves); return 0; }