import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static class RedHorseSolver { private static class Cell { int row; int col; short value; int x; int y; public Cell(int row, int col, int value) { this.row = row; this.col = col; this.value = (short) value; this.x = col; this.y = row; } @Override public String toString() { return "row (y) = " + row + ", col (x) = " + col + ", value = " + value; } } private static class Move { final int dx; final int dy; final String name; public Move(int dx, int dy, String name) { this.dx = dx; this.dy = dy; this.name = name; } @Override public String toString() { return name; } } // UL, UR, R, LR, LL, L private Move[] moves = new Move[] { new Move(-1, -2, "UL"), new Move(+1, -2, "UR"), new Move(+2, 0, "R"), new Move(+1, +2, "LR"), new Move(-1, +2, "LL"), new Move(-2, 0, "L") }; private static final int EMPTY = 0; private int[][] grid; private int[][] priority; public static class Answer { int size; String path; public Answer(int size, String path) { this.size = size; this.path = path; } } public Answer solve(int n, int i_start, int j_start, int i_end, int j_end) { grid = new int[n][]; priority = new int[n][]; for (int i = 0; i < n; i++) { grid[i] = new int[n]; priority[i] = new int[n]; } ArrayDeque cells = new ArrayDeque<>(); Cell start = new Cell(i_start, j_start, 1); cells.add(start); grid[start.row][start.col] = 1; int destValue = -1; boolean found = false; while (!cells.isEmpty() && !found) { Cell cell = cells.poll(); for (int i = 0; i < moves.length; i++) { Move move = moves[i]; int newRow = cell.row + move.dy; int newCol = cell.col + move.dx; if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n) { if (grid[newRow][newCol] != EMPTY) { continue; } grid[newRow][newCol] = cell.value + 1; priority[newRow][newCol] = priority[cell.row][cell.col] + (moves.length - i); if (newRow == i_end && newCol == j_end) { found = true; destValue = grid[newRow][newCol]; break; } cells.add(new Cell(newRow, newCol, cell.value + 1)); } } } if (!found) { return new Answer(-1, "Impossible"); } List route = new ArrayList<>(); boolean traced = false; int value = grid[i_end][j_end]; Cell pos = new Cell(i_end, j_end, value); route.add(pos); List movesList = new ArrayList<>(); while (!traced) { int maxPriority = -1; Move maxMove = null; for (Move move : moves) { int newRow = pos.row + move.dy; int newCol = pos.col + move.dx; if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n) { if (grid[newRow][newCol] != pos.value - 1) { continue; } if (priority[newRow][newCol] > maxPriority) { maxPriority = priority[newRow][newCol]; maxMove = move; } } } int newRow = pos.row + maxMove.dy; int newCol = pos.col + maxMove.dx; pos = new Cell(newRow, newCol, pos.value - 1); route.add(pos); movesList.add(maxMove); if (grid[newRow][newCol] == 1) { traced = true; } } Collections.reverse(movesList); /* List movesList = new ArrayList<>(); trace(movesList, new Cell(i_start, j_start, 1), i_end, j_end); */ StringBuilder sb = new StringBuilder(); for (int i = 0; i < movesList.size(); i++) { Move move = movesList.get(i); sb.append(getOpposite(move.name)); if (i < movesList.size() - 1) { sb.append(" "); } } Answer answer = new Answer(movesList.size(), sb.toString()); return answer; } private boolean trace(List movesList, Cell pos, int i_end, int j_end) { if (pos.row == i_end && pos.col == j_end) { return true; } int maxPriority = -1; Move maxMove = null; for (Move move : moves) { int newRow = pos.row + move.dy; int newCol = pos.col + move.dx; if (newRow >= 0 && newRow < grid.length && newCol >= 0 && newCol < grid.length) { if (grid[newRow][newCol] == pos.value + 1) { if (priority[newRow][newCol] > maxPriority) { maxPriority = priority[newRow][newCol]; maxMove = move; } } } } if (maxPriority < 0) { return false; } int newRow = pos.row + maxMove.dy; int newCol = pos.col + maxMove.dx; Cell newPos = new Cell(newRow, newCol, pos.value + 1); movesList.add(maxMove); boolean traced = trace(movesList, newPos, i_end, j_end); if (traced) { return true; } movesList.remove(movesList.size() - 1); return false; } private String getOpposite(String name) { if ("LR".equals(name)) { return "UL"; } else if ("L".equals(name)) { return "R"; } else if ("R".equals(name)) { return "L"; } else if ("LL".equals(name)) { return "UR"; } else if ("UL".equals(name)) { return "LR"; } else if ("UR".equals(name)) { return "LL"; } return null; } private void debugPrint(int n) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { String value = String.format("%02d ", grid[i][j]); System.out.print(value); } System.out.println(); } System.out.println(); } } static void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { Solution.RedHorseSolver solver = new Solution.RedHorseSolver(); RedHorseSolver.Answer answer = solver.solve(n, i_start, j_start, i_end, j_end); if (answer.size > 0) { System.out.println(answer.size); } System.out.println(answer.path); } 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(); } }