import javafx.geometry.Pos; import java.util.*; import java.util.stream.Collectors; public class redKnight { static HashSet visited = new HashSet<>(); static String bestMove = ""; static class Move{ double cost; Position from; Position to; public Move(Position from, Position to, Position end) { this.from = from; this.to = to; this.cost = costOf(to, end); } double costOf(Position from, Position to){ return Math.pow(to.i - from.i, 2) + Math.pow(to.j - from.j, 2); } } static class SortByCost implements Comparator { // Used for sorting in ascending order of // roll number public int compare(Move a, Move b) { if (a.cost < b.cost) return -1; if (a.cost == b.cost) return 0; return 1; } } static class Position{ @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Position position = (Position) o; return i == position.i && j == position.j; } @Override public int hashCode() { return Objects.hash(i, j); } public Position(int i, int j) { this.i = i; this.j = j; this.desc = ""; } int i; int j; String desc; public Position(int i, int j, String desc) { this.i = i; this.j = j; this.desc = desc; } } 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(); if (!isValidMove(i_start, j_start, i_end, j_end)) { System.out.println("Impossible"); return; } printShortestPath(n, i_start, j_start, i_end, j_end); in.close(); } 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. Position start = new Position(i_start, j_start); Position end = new Position(i_end, j_end); move(start, end, n); System.out.println(visited.size()); System.out.println(bestMove); // System.out.println(4); } static List generateMoves(Position pos, int n) { ArrayList moves = new ArrayList<>(); int i = pos.i; int j = pos.j; moves.add(new Position(i-2, j-1, "UL")); moves.add(new Position(i - 2, j+1, "UR")); moves.add(new Position(i, j+2, "R")); moves.add(new Position(i+2, j+1, "LR")); moves.add(new Position(i+2, j-1, "LL")); moves.add(new Position(i, j - 2, "L")); return moves.stream().filter((p) -> { boolean b = p.i < n && p.i >= 0 && p.j < n && p.j >= 0; return b; }).collect(Collectors.toList()); } static String move(Position start, Position end, int n){ if (start.equals(end)) return start.desc; // if (visited.size() > 500){ // return null; // return what it is at that point // } visited.add(start); // 1. generate all relevant moves List allPossiblePos = generateMoves(start, n); List allMoves = new ArrayList<>(); // pick move closest to target for (Position pos : allPossiblePos){ allMoves.add(new Move(start, pos, end)); } Collections.sort(allMoves, new SortByCost()); Position bestPos = allMoves.get(0).to; bestMove += (bestPos.desc) + " "; move(bestPos, end, n); return ""; } static boolean isValidMove(int i_start, int j_start, int i_end, int j_end){ if (i_end % 4 == i_start % 4) { // same plane, so match cardinality of j return j_start % 2 == j_end % 2; } else if (i_end % 2 == i_start % 2){ // opposite cardinality of j return j_start % 2 != j_end % 2; } else { // completely off plane, false return false; } } }