using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution { static int ipos, jpos; static int moves = 0; static string result; static string output; static string failString = "Impossible"; static int count = 0; static bool stillMoving = true; static int rightmoves = 0; static int leftmoves = 0; //check if out of bounds or instant fail static bool FailTest(int n, int i, int iEnd, int j, int jEnd) { bool failure = false; //check if out of bounds if(i < 0 || i > n || iEnd < 0 || iEnd > n || j < 0 || j > n || jEnd < 0 || jEnd > n) { failure = true; } //check if start and end position are the same if(i == iEnd && j == jEnd) { failure = true; } return failure; } static bool canMoveRight(int jEnd, int j) { if((jEnd - j) % 2 == 0) { return true; } else { return false; } } static bool canMoveLeft(int j, int jEnd) { if((j - jEnd) % 2 == 0) { return true; } else { return false; } } static void GetRightMoves(int jEnd, int j) { rightmoves += (jEnd - j) / 2; for (int i = 0; i < rightmoves; i++) { result += "R "; moves++; } jpos += rightmoves * 2; } static void GetLeftMoves(int j, int jEnd) { leftmoves += (j - jEnd) / 2; for(int i = 0; i < leftmoves; i++) { result += "L "; moves++; } jpos -= leftmoves * 2; } //going left and up move ipos - 2 and jpos - 1 and update result and moves static void setPosUL(int i, int j, string direction) { ipos = i - 2; jpos = j - 1; result += direction; moves++; } //going right and up move ipos - 2 and jpos + 1 and update result and moves static void setPosUR(int i, int j, string direction) { ipos = i - 2; jpos = j + 1; result += direction; moves++; } //going right and down move ipos + 2 and jpos + 1 update results and moves static void setPosLR(int i, int j, string direction) { ipos = i + 2; jpos = j + 1; result += direction; moves++; } //going left and down move ipos + 2 and jpos - 1 update results and moves static void setPosLL(int i, int j, string direction) { ipos = i + 2; jpos = j - 1; result += direction; moves++; } static 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. //set ipos and jpos as starting points for now ipos = i_start; jpos = j_start; // Is problem valid or is it Impossible bool isNotPossible = FailTest(n, i_start, i_end, j_start, j_end); if (isNotPossible) { result = failString; } //test for movement route and number of moves else { //loop till meet at end point or loop > 200 times for fail while (stillMoving) { if(count >= 200) { result = failString; stillMoving = false; break; } //check if we can just move left or right if (ipos == i_end) { // we can just go right or left // if start is smaller than end go right if (jpos < j_end) { //check if right movement is possible or not bool moveRightPossible = canMoveRight(j_end, jpos); //we can actually move right if (moveRightPossible) { GetRightMoves(j_end, jpos); } //move right not possible else { result = failString; stillMoving = false; break; } } // else if start is bigger than end then go left else if (jpos > j_end) { //check if left movement is possible or not bool moveLeftPossible = canMoveLeft(jpos, j_end); //we can actually move left if (moveLeftPossible) { GetLeftMoves(jpos, j_end); } //left move not possible else { result = failString; stillMoving = false; break; } } } //check for up or down movement else if (ipos > i_end) { //going up //check for left or right if (jpos > j_end) { //going left and up move ipos - 2 and jpos - 1 and update result and moves setPosUL(ipos, jpos, "UL "); } else if (jpos < j_end) { //going right and up move ipos - 2 and jpos + 1 and update result and moves setPosUR(ipos, jpos, "UR "); } } else if(ipos < i_end) { //going down //check for right or left if(jpos < j_end) { //going right and down move ipos + 2 and jpos + 1 setPosLR(ipos, jpos, "LR "); } else if(jpos > j_end) { //going left and down move ipos + 2 and jpos - 1 update results and moves setPosLL(ipos, jpos, "LL "); } } if (ipos == i_end && jpos == j_end) { stillMoving = false; } count++; } } //print result if result == failString else build and print output if(result == failString) { Console.WriteLine(result); } else { output = String.Format("{0} \n{1}", moves, result); Console.WriteLine(output); } } static void Main(String[] args) { int n = Convert.ToInt32(Console.ReadLine()); string[] tokens_i_start = Console.ReadLine().Split(' '); int i_start = Convert.ToInt32(tokens_i_start[0]); int j_start = Convert.ToInt32(tokens_i_start[1]); int i_end = Convert.ToInt32(tokens_i_start[2]); int j_end = Convert.ToInt32(tokens_i_start[3]); printShortestPath(n, i_start, j_start, i_end, j_end); } }