import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { @SuppressWarnings("unchecked") 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. boolean[][] visited = new boolean[n][n]; for(int i = 0 ; i < n ; i++) for(int j = 0 ; j < n ; j++) visited[i][j] = false; Position goal = new Position(i_end, j_end, n, Movement.GOAL); Position start = new Position(i_start, j_start, n, Movement.START, goal, null); List moves = new ArrayList(); Stack positionsStack = new Stack(); Stack movStack = new Stack(); Stack finalMovStack = null; moves.add(start); moves.addAll(getNextPositions(start, goal) ); int lastDistanceToGoal = Integer.MAX_VALUE; for(Position pos : moves) { emptyStacks(positionsStack, movStack); int distanceToGoal = analysePaths(visited, goal, pos, positionsStack, movStack); if(lastDistanceToGoal > distanceToGoal) { lastDistanceToGoal = distanceToGoal; finalMovStack = (Stack) movStack.clone(); } } if(lastDistanceToGoal != 0) { System.out.println("Impossible"); return; } String movs = ""; System.out.println(finalMovStack.size()-1); while(!finalMovStack.empty() ) { movs += finalMovStack.firstElement()+" "; finalMovStack.remove(finalMovStack.firstElement() ); } System.out.println(movs.trim()); } private static void emptyStacks(Stack positionsStack, Stack movStack) { while(positionsStack.size() > 1) positionsStack.pop(); while(!movStack.empty()) movStack.pop(); } private static int analysePaths(boolean[][] visited, Position goal, Position posToGetPaths, Stack positionsStack, Stack movStack) { List nextPositionsList = null; Position p = posToGetPaths; int minorDistanceToGoal = Integer.MAX_VALUE; while(!p.equals(goal) ) { // enquanto nao analisou todos os moves if(!visited[p.getLine()][p.getCol()]) { visited[p.getLine()][p.getCol()] = true; if(p.distanceToGoal() < minorDistanceToGoal) { positionsStack.push(p); movStack.push(p.getMovement()); minorDistanceToGoal = p.distanceToGoal(); } nextPositionsList = getNextPositions(positionsStack.peek(), goal); p = getCloserPosition(nextPositionsList, goal); } if(p.equals(goal)) { minorDistanceToGoal = 0; movStack.push(p.getMovement()); } else if(p.distanceToGoal() >= minorDistanceToGoal) { minorDistanceToGoal = Integer.MAX_VALUE; break; } else if(visited[p.getLine()][p.getCol()]) { minorDistanceToGoal = Integer.MAX_VALUE; break; } } return minorDistanceToGoal; } private static Position getCloserPosition(List nextPositionsList, Position goal) { Position closer = nextPositionsList.get(0); for(int i = 1; i < nextPositionsList.size(); i++) { if(nextPositionsList.get(i).distanceToGoal() < closer.distanceToGoal()) { closer = nextPositionsList.get(i); } } return closer; } public static List getNextPositions(Position p, Position goal) { List moves = new ArrayList(); Position ul = null; Position ur = null; Position r = null; Position lr = null; Position ll = null; Position l = null; try { ul = p.moveUpperLeft(goal); moves.add(ul); } catch(Exception e) { /*System.err.println("ERR UL "+e.getMessage());*/ } try { ur = p.moveUpperRight(goal); moves.add(ur); } catch(Exception e) { /*System.err.println("ERR UR "+e.getMessage());*/ } try { r = p.moveRight(goal); moves.add(r); } catch(Exception e) { /*System.err.println("ERR R "+e.getMessage());*/ } try { lr = p.moveLowerRight(goal); moves.add(lr); } catch(Exception e) { /*System.err.println("ERR LR "+e.getMessage());*/ } try { ll = p.moveLowerLeft(goal); moves.add(ll); } catch(Exception e) { /* System.err.println("ERR LL "+e.getMessage()); */ } try { l = p.moveLeft(goal); moves.add(l); } catch(Exception e) { /* System.err.println("ERR L "+e.getMessage()); */ } return moves; } 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(); } } class Position { int line; int col; int tamTab; boolean visited; Movement mov; final Position goal; Position parent; public Position(int i, int j, int n, Movement m) { if(!m.getValue().equals("GOAL")) throw new RuntimeException("GOAL must be constructed"); if(i < 0 || i >= n) throw new RuntimeException("Invalid value for line: "+i+" (table = "+n+")"); else if(j < 0 || j >= n) throw new RuntimeException("Invalid value for column: "+j+" (table = "+n+")"); this.line = i; this.col = j; tamTab = n; visited = false; mov = m; goal = this; } public Position(int i, int j, int n, Movement m, Position goal, Position parent) { if(i < 0 || i >= n) throw new RuntimeException("Invalid value for line: "+i+" (table = "+n+")"); else if(j < 0 || j >= n) throw new RuntimeException("Invalid value for column: "+j+" (table = "+n+")"); this.line = i; this.col = j; tamTab = n; visited = false; mov = m; this.goal = goal; this.parent = parent; } public int distanceToGoal() { return Math.abs(getLine()-goal.getLine()) + Math.abs(getCol()-goal.getCol()) ; } public void setVisited(boolean visited) { this.visited = visited; } public boolean isVisited() { return this.visited; } public String getMovement() { return mov.getValue(); } public int getLine() { return line; } public int getCol() { return col; } public Position moveLeft(Position goal) { return new Position(line, col-2, tamTab, Movement.LEFT, goal, this); } public Position moveRight(Position goal) { return new Position(line, col+2, tamTab, Movement.RIGHT, goal, this); } public Position moveUpperLeft(Position goal) { return new Position(line-2, col-1, tamTab, Movement.UPPER_LEFT, goal, this); } public Position moveUpperRight(Position goal) { return new Position(line-2, col+1, tamTab, Movement.UPPER_RIGHT, goal, this); } public Position moveLowerRight(Position goal) { return new Position(line+2, col+1, tamTab, Movement.LOWER_RIGHT, goal, this); } public Position moveLowerLeft(Position goal) { return new Position(line+2, col-1, tamTab, Movement.LOWER_LEFT, goal, this); } @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + col; result = prime * result + line; return result; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; Position other = (Position) obj; if (col != other.col) return false; if (line != other.line) return false; return true; } } enum Movement { UPPER_LEFT ("UL"), UPPER_RIGHT ("UR"), RIGHT ("R"), LOWER_RIGHT ("LR"), LOWER_LEFT ("LL"), LEFT ("L"), GOAL ("GOAL"), START (""); private final String value; private Movement(final String value) { this.value = value; } public String getValue() { return value; } }