import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; class Node { private int x; private int y; private int dist; private String lastMove; private Node previous; //Constructor for nodes (distance has a starting value of -1 for all except S) public Node( int cx, int cy) { x = cx; y = cy; dist = -1; lastMove = ""; previous = null; } //Accessors public int getX() {return x;} public int getY() {return y;} public int getDist() {return dist;} public String getLM() {return lastMove;} public Node getPrev() {return previous;} //Mutators public void setDist(int newDist) {dist = newDist;} public void setMove(String lm) {lastMove = lm;} public void setPrev(Node prev) {previous = prev;} // Check if node needs to be updated (distance -1 if never seen) public boolean check(int newDist) { return ((dist > newDist) || (dist == -1)); } /* Override equals to check only for coordinates * (apart from self/null reference or different class, * where behavior is not expected to change). */ @Override public boolean equals(Object other) { if(this == other) return true; if((other == null) || getClass() != other.getClass()) return false; Node temp = (Node) other; return (this.x == temp.x) && (this.y == temp.y); } @Override public int hashCode() { int result = x; result = 31*result + y; return result; } } class Move implements Comparable { private Node next; //Next node to check private int dist; //Distance when it was seen private long co; public Node getNext() {return next;} public Move(Node n, int d,long c) { next = n; dist = d; co=c; } // Comparison function, for priority queue sorting @Override public int compareTo(Move other) { if (dist < other.dist) return -1; else if (dist > other.dist) return 1; else { if(co other.next.getX()) return -1; // else { // if (next.getY() < other.next.getY()) return 1; // else if (next.getY() > other.next.getY()) return -1; // else return 0; // } } } } class Solver { private Node[][] map; private Node start; private Node end; private int N; private int M; // Constructor for Solver, which reads the map and constructs the nodes public Solver(int R,int i_start,int j_start,int i_end, int j_end) throws IOException { N=R; M=R; map = new Node[N][N]; start= new Node(i_start,j_start); end= new Node (i_end,j_end); for(int i=0;i seen = new HashSet<>(); // Hash set for nodes already seen. PriorityQueue open = new PriorityQueue<>(); // Priority queue of Move objects (open set) open.add(new Move(start,0,0)); int count=0; int i=0; int cc=0; while(!open.isEmpty()) { i++; Move nextMove = open.peek(); // Get next move Node current = nextMove.getNext(); // and its node. open.remove(); int currX = current.getX(); int currY = current.getY(); // System.out.println(i+" "+currX + " " +currY+ " "+ current.getDist()); if(currX==end.getY() && currY==end.getX()){ System.out.println(current.getDist()+1); StringBuilder path = new StringBuilder(); // Construct string of moves from finish to start while(!current.equals(start)) { path.append(current.getLM()); current = current.getPrev(); if(!current.equals(start))path.append(" "); } path = path.reverse(); // Reverse for correct order System.out.println(path.toString()); cc=1; break; } if(!seen.contains(current)) { // If not E and not seen, seen.add(current); // it is added to seen set. if(currX > 1 && currY > 0) { // Check if neighbors need to be updated int newDist = current.getDist() + 1; // (by use of check method and if they are not in the seen set) Node neigh = map[currX-2][currY-1]; if(neigh.check(newDist) && !seen.contains(neigh)) { neigh.setDist(newDist); // Update values. neigh.setMove("LU"); neigh.setPrev(current); count++; open.add(new Move(neigh,newDist,count)); // System.out.println("AAAA");// Add neighbor to open set } }//ok if(currX > 1 && currY < M-1) { // Same for the rest int newDist = current.getDist() + 1; Node neigh = map[currX-2][currY+1]; if(neigh.check(newDist) && !seen.contains(neigh)) { neigh.setDist(newDist); neigh.setMove("RU"); neigh.setPrev(current); count++; open.add(new Move(neigh,newDist,count)); } }//ok if(currY < M-2) { int newDist = current.getDist() + 1; Node neigh = map[currX][currY+2]; if(neigh.check(newDist) && !seen.contains(neigh)) { neigh.setDist(newDist); neigh.setMove("R"); neigh.setPrev(current); count++; open.add(new Move(neigh,newDist,count)); } }//ok if(currY < M-1 && currX < N-2) { int newDist = current.getDist() + 1; Node neigh = map[currX+2][currY+1]; if(neigh.check(newDist) && !seen.contains(neigh)) { neigh.setDist(newDist); neigh.setMove("RL"); neigh.setPrev(current); count++; open.add(new Move(neigh,newDist,count)); } }//ok if(currY > 0 && currX < N-2) { int newDist = current.getDist() + 1; Node neigh = map[currX+2][currY-1]; if(neigh.check(newDist) && !seen.contains(neigh)) { neigh.setDist(newDist); neigh.setMove("LL"); neigh.setPrev(current); count++; open.add(new Move(neigh,newDist,count)); } }//ok if(currY > 1) { int newDist = current.getDist() + 1; Node neigh = map[currX][currY-2]; if(neigh.check(newDist) && !seen.contains(neigh)) { neigh.setDist(newDist); neigh.setMove("L"); neigh.setPrev(current); count++; open.add(new Move(neigh,newDist,count)); } }//ok } } if(cc==0) System.out.println("Impossible"); } } 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. Solver s; try { s = new Solver(n,j_start,i_start,j_end,i_end); s.Solve(); } catch (IOException e) { // TODO Auto-generated catch block System.out.println("Bad input."); } } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int j_start = in.nextInt(); int i_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(); } }