import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { static void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { int[][] voronoi = new int[n][n]; for (int i = 0; i < n; i++){ Arrays.fill(voronoi[i], 30000); } int currentIndex = 0; int addedObjects = 0; int[][] open = new int[10000][2]; open[addedObjects][0] = i_end; open[addedObjects][1] = j_end; voronoi[i_end][j_end] = 0; addedObjects++; boolean stop = false; while (!stop &¤tIndex < addedObjects) { int[] current = open[currentIndex++]; int currentValue = voronoi[current[0]][current[1]]; int[][] neighbours = getNeighbours(n, current); for (int[] ne : neighbours) { if (voronoi[ne[0]][ne[1]] > currentValue+1) { voronoi[ne[0]][ne[1]] = currentValue+1; //System.err.println(ne[0]+"/"+ne[1] +" = "+ (currentValue+1)); if (ne[0] == i_start && ne[1] == j_start) { //stop = true; } open[addedObjects++] = ne; } } } int pathLength = voronoi[i_start][j_start]; System.err.println(pathLength); if (pathLength == 30000) { System.out.println("Impossible"); return; } System.out.println(pathLength); int[] current = new int[] {i_start, j_start}; StringBuilder builder = new StringBuilder(); while (current[0] != i_end || current[1] != j_end) { int value = voronoi[current[0]][current[1]]; int[][] neighbours = getNeighbours(n, current); for(int[] ne : neighbours) { if (value -1 == voronoi[ne[0]][ne[1]]) { String m = points2movement(current, ne); System.err.println(m); if (builder.length() > 0) builder.append(" "); builder.append(m); current = ne; break; } } } System.out.println(builder); } static String points2movement(int[] a, int[] b) { if (a[1] == b[1]-2) { return "R"; } if (a[1] == b[1]+2) { return "L"; } if (a[1] == b[1]+1 && a[0] == b[0] -2) { return "LL"; } if (a[1] == b[1]+1 && a[0] == b[0] +2) { return "UL"; } if (a[1] == b[1]-1 && a[0] == b[0] -2) { return "LR"; } if (a[1] == b[1]-1 && a[0] == b[0] +2) { return "UR"; } return "M"; } // UL, UR, R, LR, LL, L static int[][] getNeighbours(int n, int[] current) { List list = new ArrayList<>(); if (current[0]-2 >= 0) { if (current[1]-1 >= 0) { list.add(new int[]{current[0]-2, current[1]-1}); } if (current[1]+1 < n) list.add(new int[]{current[0]-2, current[1]+1}); } if (current[1] + 2 < n) list.add(new int[]{current[0], current[1]+2}); if (current[0]+2 < n) { if (current[1]+1 < n) { list.add(new int[]{current[0]+2, current[1]+1}); } if ((current[1]-1) >= 0) list.add(new int[]{current[0]+2, current[1]-1}); } if (current[1] - 2 >= 0) { list.add(new int[]{current[0], current[1]-2}); } int[][] array = new int[list.size()][2]; for (int i = 0; i < list.size(); i++) { //System.err.println("n "+ list.get(i)[0]+" "+ list.get(i)[1] ); array[i] = list.get(i); } return array; } 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(); } }