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) { // Print the distance along with the sequence of moves. // Print the distance along with the sequence of moves. int[][] chess = new int[n][n]; chess[i_end][j_end]=1; int[][] r_path = new int[n][n]; int[][] c_path = new int[n][n]; int[][] path = new int[n][n]; String[] pathSymbol = {"UL","UR","R","LR","LL","L"}; Queue step = new LinkedList<>(); step.add(new int[]{i_end,j_end}); while(!step.isEmpty()){ int[] move = step.poll(); int r_end = move[0]; int c_end = move[1]; int distance = chess[r_end][c_end]+1; //6 moves if(c_end-2 >=0){//L if(chess[r_end][c_end-2]==0||chess[r_end][c_end-2]>distance ||(chess[r_end][c_end-2]==distance && path[r_end][c_end-2]>2)){ chess[r_end][c_end-2]=distance; step.add(new int[]{r_end,c_end-2}); r_path[r_end][c_end-2]=r_end; c_path[r_end][c_end-2]=c_end; path[r_end][c_end-2]=2;//R } } if(c_end+2distance){ chess[r_end][c_end+2]=distance; step.add(new int[]{r_end,c_end+2}); r_path[r_end][c_end+2]=r_end; c_path[r_end][c_end+2]=c_end; path[r_end][c_end+2]=5;//L } } if(r_end-2>=0){//U if( c_end-1>=0 ){//UL if(chess[r_end-2][c_end-1]==0||chess[r_end-2][c_end-1]>=distance ||(chess[r_end-2][c_end-1]==distance && path[r_end-2][c_end-1]>3)){ chess[r_end-2][c_end-1]=distance; step.add(new int[]{r_end-2,c_end-1}); r_path[r_end-2][c_end-1]=r_end; c_path[r_end-2][c_end-1]=c_end; path[r_end-2][c_end-1]=3; } } if( c_end+1distance ||(chess[r_end-2][c_end+1]==distance && path[r_end-2][c_end+1]>4)){ chess[r_end-2][c_end+1]=distance; step.add(new int[]{r_end-2,c_end+1}); r_path[r_end-2][c_end+1]=r_end; c_path[r_end-2][c_end+1]=c_end; path[r_end-2][c_end+1]=4; } } } if(r_end+2=0){//LL if(chess[r_end+2][c_end-1]==0||chess[r_end+2][c_end-1]>distance ||(chess[r_end+2][c_end-1]==distance && path[r_end+2][c_end-1]>1)) { chess[r_end+2][c_end-1]=distance; step.add(new int[]{r_end+2,c_end-1}); r_path[r_end+2][c_end-1]=r_end; c_path[r_end+2][c_end-1]=c_end; path[r_end+2][c_end-1]=1; } } if(c_end+1=distance) { chess[r_end+2][c_end+1]=distance; step.add(new int[]{r_end+2,c_end+1}); r_path[r_end+2][c_end+1]=r_end; c_path[r_end+2][c_end+1]=c_end; path[r_end+2][c_end+1]=0; } } } } if(chess[i_start][j_start]>0){ System.out.println(chess[i_start][j_start]-1); int r_next=i_start; int c_next=j_start; while ((r_path[r_next][c_next]!=i_end) || (c_path[r_next][c_next]!=j_end)){ System.out.print(pathSymbol[path[r_next][c_next]]+" "); int tmp_r = r_next; int tmp_c = c_next; r_next=r_path[tmp_r][tmp_c]; c_next=c_path[tmp_r][tmp_c]; } System.out.print(pathSymbol[path[r_next][c_next]]+" "); //print the step back } else { System.out.print("Impossible"); } } 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(); } }