import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Solution { private static String impos = "Impossible"; private static boolean[][] chessboard = null; private static Queue stack = new LinkedList(); public static void main(String[] args) { // TODO Auto-generated method stub Scanner s = new Scanner(System.in); int matrix = s.nextInt(); chessboard = new boolean[matrix][matrix]; int startx = s.nextInt(); int starty = s.nextInt(); int destx = s.nextInt(); int desty = s.nextInt(); Point startp = new Point(); startp.locx = startx; startp.locy = starty; startp.count = 0; startp.priopath = ""; Point destination = new Point(); destination.locx = destx; destination.locy = desty; stack.add(startp); chessboard[startx][starty] = true; Point ans = null; while(!stack.isEmpty()){ ans = knightTraversal(stack.poll(),destination,matrix-1); if(ans != null)break; } if(ans != null){ System.out.println(ans.count); System.out.println(ans.priopath); }else{ System.out.println(impos); } } private static Point knightTraversal(Point nextMove,Point destination,int matrix){//matrix = -1 Point found = null; //UL int upperx = nextMove.locx - 2; int upperLeft = nextMove.locy - 1; if(upperx >=0 && upperLeft >= 0 && !chessboard[upperx][upperLeft] ){ chessboard[upperx][upperLeft] = true; Point uppermove = new Point(); uppermove.locx = upperx; uppermove.locy = upperLeft; uppermove.count = nextMove.count + 1; uppermove.priopath = nextMove.priopath + "UL "; stack.add(uppermove); if(upperx == destination.locx && upperLeft == destination.locy){ uppermove.priopath.trim(); found = uppermove; return found; } // found = knightTraversal(stack.pop(),destination,matrix-1); } //UR int upperRight = nextMove.locy + 1; if(upperx >=0 && upperRight <= matrix && !chessboard[upperx][upperRight] ){ chessboard[upperx][upperRight] = true; Point uppermove = new Point(); uppermove.locx = upperx; uppermove.locy = upperRight; uppermove.count = nextMove.count + 1; uppermove.priopath = nextMove.priopath + "UR "; stack.add(uppermove); if(upperx == destination.locx && upperRight == destination.locy){ uppermove.priopath.trim(); found = uppermove; return found; } // found = knightTraversal(stack.pop(),destination,matrix-1); } //R int pureright = nextMove.locy + 2; int currentpos = nextMove.locx; if(pureright <= matrix && !chessboard[currentpos][pureright]){ chessboard[currentpos][pureright] = true; Point uppermove = new Point(); uppermove.locx = currentpos; uppermove.locy = pureright; uppermove.count = nextMove.count + 1; uppermove.priopath = nextMove.priopath + "R "; stack.add(uppermove); if(currentpos == destination.locx && pureright == destination.locy){ uppermove.priopath.trim(); found = uppermove; return found; } // found = knightTraversal(stack.pop(),destination,matrix-1); } //LR int lowerx = nextMove.locx + 2; int lowerRight = nextMove.locy + 1; if(lowerx <= matrix && lowerRight <= matrix && !chessboard[lowerx][lowerRight]){ chessboard[lowerx][lowerRight] = true; Point uppermove = new Point(); uppermove.locx = lowerx; uppermove.locy = lowerRight; uppermove.count = nextMove.count + 1; uppermove.priopath = nextMove.priopath + "LR "; stack.add(uppermove); if(lowerx == destination.locx && lowerRight == destination.locy){ uppermove.priopath.trim(); found = uppermove; return found; } // found = knightTraversal(stack.pop(),destination,matrix-1); } //LL int lowerLeft = nextMove.locy - 1; if(lowerx <= matrix && lowerLeft >= 0 && !chessboard[lowerx][lowerLeft]){ chessboard[lowerx][lowerLeft] = true; Point uppermove = new Point(); uppermove.locx = lowerx; uppermove.locy = lowerLeft; uppermove.count = nextMove.count + 1; uppermove.priopath = nextMove.priopath + "LL "; stack.add(uppermove); if(lowerx == destination.locx && lowerLeft == destination.locy){ uppermove.priopath.trim(); found = uppermove; return found; } // found = knightTraversal(stack.pop(),destination,matrix-1); } //L int pureleft = nextMove.locy - 2; int currentposx = nextMove.locx; if(pureleft >= 0 && !chessboard[currentposx][pureleft]){ chessboard[currentposx][pureleft] = true; Point uppermove = new Point(); uppermove.locx = currentposx; uppermove.locy = pureleft; uppermove.count = nextMove.count + 1; uppermove.priopath = nextMove.priopath + "L "; stack.add(uppermove); if(currentposx == destination.locx && pureleft == destination.locy){ uppermove.priopath.trim(); found = uppermove; return found; } // found = knightTraversal(stack.pop(),destination,matrix-1); } return found; } } class Point{ int locx; int locy; int count; String priopath; }