import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { static Coordinate start; static Coordinate end; static int[] row = {-2, -2, 0, 2, 2, 0}; static int[] col = {-1, 1, 2, 1, -1, -2}; static ArrayList coordinates = new ArrayList<>(); // Prints the distance along with the sequence of moves. static void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { // Create HashMap of visited coordinates HashMap visited = new HashMap<>(); // Start and end coordinates start = new Coordinate(i_start, j_start); end = new Coordinate(i_end, j_end); // Create the queue and add the start coordinate Queue queue = new LinkedList(); queue.add(start); while (!queue.isEmpty()) { Coordinate current = queue.poll(); int x = current.x; int y = current.y; int distance = current.distance; int hash = Integer.parseInt("" + x + y); if (x == end.x && y == end.y) { end.distance = distance; System.out.println(distance); printPath(start, 0); // Set current distance to 0 break; } // Check possible coordinates the knight can jump to if (!visited.containsKey(hash)) { // Mark the coordinate as visited visited.put(hash, true); // Add coordinates to the path coordinates.add(current); // Get the other possible coordinates and enqueue them for (int i = 0; i < 6; i++) { int x1 = x + row[i]; int y1 = y + col[i]; if (isValid(x1, y1, n)) { queue.add(new Coordinate(x1, y1, distance + 1)); } } } } // An empty queue means that there is no possible path from start to end if (queue.isEmpty()) { System.out.println("Impossible"); } } private static void printPath(Coordinate current, int numMoves) { numMoves++; // Base case if (numMoves == end.distance) { String result = movement(current, end); System.out.print(result); } // Recursive case else { int minIndex = 0; // Index of the coordinate with the shortest distance int minDistance = distance(coordinates.get(0)); for (int i = 0; i < coordinates.size(); i++) { Coordinate c = coordinates.get(i); if (c.distance > numMoves) { break; } if (c.distance == numMoves && distance(c) < minDistance) { minIndex = i; minDistance = distance(c); } } Coordinate next = coordinates.get(minIndex); String result = movement(current, next) + " "; System.out.print(result); printPath(next, numMoves); } } // Determines if the coordinate is on the board private static boolean isValid(int x, int y, int n) { if (x < 0 || y < 0 || x >= n || y >= n) { return false; } return true; } // Calculates the distance between the coordinate and the end coordinate private static int distance(Coordinate start) { int x = Math.abs(start.x - end.x); int y = Math.abs(start.y - end.y); return x + y; } // Calculates the result of the movement as a string (UL, UR, R, LR, LL, L) private static String movement(Coordinate current, Coordinate next) { String result = ""; if (current.y < next.y) { // We moved right if (current.x == next.x) { result = "R"; } else if (current.x < next.x) { result = "LR"; // We moved down } else if (current.x > next.x) { result = "UR"; // We moved up } } else if (current.y > next.y) { // We moved left if (current.x == next.x) { result = "L"; } else if (current.x < next.x) { result = "LL"; // We moved down } else if (current.x > next.x) { result = "UL"; // We moved up } } return result; } private static class Coordinate { int x, y, distance; // Default constructor public Coordinate(int x, int y) { this.x = x; this.y = y; } // Secondary constructor public Coordinate(int x, int y, int distance) { this.x = x; this.y = y; this.distance = distance; } public String toString() { return x + " " + y + " " + distance; } } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int i_start = in.nextInt(); int j_start = in.nextInt(); int i_end = in.nextInt(); int j_end = in.nextInt(); printShortestPath(n, i_start, j_start, i_end, j_end); in.close(); } }