/** * Created by Chezlui on 15/12/2017. */ import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Solution { // UL, UR, R, LR, LL, L public static final int UL = 1; public static final int UR = 2; public static final int R = 3; public static final int LR = 4; public static final int LL = 5; public static final int L = 6; public static final int ORIGIN = 0; public static int shortestPath = Integer.MAX_VALUE; public static final int[] movements = {UL, UR, R, LR, LL, L}; public static final String[] litMoves = {"", "UL", "UR", "R", "LR", "LL", "L"}; static ArrayList> paths = new ArrayList<>(); static void makeMovements(int n, Node node, Point origin, Point destination, int move) { Node newNode = Node.translateAndAddStep(node, move); if (move != ORIGIN && node.visitedPoints.contains(newNode.p)) { return; // Loop } else if (newNode.p.x == destination.x && newNode.p.y == destination.y) { paths.add(newNode.steps); if (shortestPath > newNode.steps.size()) { shortestPath = newNode.steps.size(); } return; // destination reached } else if (newNode.p.x < 0 || newNode.p.y < 0 || newNode.p.x >= n || newNode.p.y >= n) { return; // out of table } else if (Math.abs(destination.x - origin.x) + 2 < Math.abs(destination.x - newNode.p.x) || Math.abs(destination.y - origin.y) + 2 < Math.abs(destination.y - newNode.p.y)) { return; // wrongdirection } else if (Math.abs(destination.x - newNode.p.x) == 1 && Math.abs(destination.y - newNode.p.y) == 1) { return; // Too close won't reach } else if (newNode.steps.size() > shortestPath) { return; // long path } else { if (destination.x - newNode.p.x < 0 && destination.y - newNode.p.y <= 0) { makeMovements(n, newNode, origin, destination, UL); } else if (destination.x - newNode.p.x < 0 && destination.y - newNode.p.y > 0) { makeMovements(n, newNode, origin, destination, UR); } else if (destination.x - newNode.p.x == 0 && destination.y - newNode.p.y > 0) { makeMovements(n, newNode, origin, destination, R); } else if (destination.x - newNode.p.x > 0 && destination.y - newNode.p.y >= 0) { makeMovements(n, newNode, origin, destination, LR); } else if (destination.x - newNode.p.x > 0 && destination.y - newNode.p.y < 0) { makeMovements(n, newNode, origin, destination, LL); } else { makeMovements(n, newNode, origin, destination, L); } return; } } static void removeLongPaths() { int minimumSize = Integer.MAX_VALUE; for (ArrayList array : paths) { if (array.size() < minimumSize) { minimumSize = array.size(); } } ArrayList> aux = new ArrayList<>(); for (ArrayList array : paths) { if (array.size() > minimumSize) { aux.add(array); } } paths.removeAll(aux); } static void printPaths() { if (paths.size() == 0) { System.out.println("Impossible"); return; } ArrayList myPath = paths.get(0); myPath.remove(""); System.out.println(myPath.size()); for (String string : myPath) { System.out.print(string + " "); } } 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. // Avoid impossibles: // int xDist = Math.abs(i_end - i_start); // int yDist = Math.abs(j_end - j_start); // // if (xDist % 2 == 1 || ((xDist % 2 == 0) && (yDist % 2 == 1))) { // System.out.println("Impossible"); // return; // } Node origin = new Node(new Point(i_start, j_start), new ArrayList<>(), ORIGIN, new ArrayList<>()); makeMovements(n, origin, new Point(i_start, j_start), new Point(i_end, j_end), ORIGIN); removeLongPaths(); printPaths(); } 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(); } private static class Point { final int x; public Point(int x, int y) { this.x = x; this.y = y; } @Override public boolean equals(Object obj) { if (obj instanceof Point) { Point aux = (Point) obj; return aux.x == this.x && aux.y == this.y; } return false; } final int y; } private static class Node { public List children = new ArrayList(); final public ArrayList steps; final public Point p; public ArrayList visitedPoints; final int lastMovement; public Node(Point p, ArrayList steps, int lastMovement, ArrayList visitedPoints) { this.p = p; this.steps = steps; this.visitedPoints = new ArrayList<>(visitedPoints); this.lastMovement = lastMovement; } static Node translateAndAddStep(Node previousNode, int move) { ArrayList aux = new ArrayList<>(previousNode.steps); aux.add(litMoves[move]); int incX = 0, incY = 0; switch (move) { case UL: incX = -2; incY = -1; break; case UR: incX = -2; incY = 1; break; case R: incX = 0; incY = 2; break; case LR: incX = 2; incY = 1; break; case LL: incX = 2; incY = -1; break; case L: incX = 0; incY = -2; break; } Point p = new Point(previousNode.p.x + incX, previousNode.p.y + incY); Node n = new Node(p, aux, move, previousNode.visitedPoints); if (n != null) { n.visitedPoints.add(p); } return n; } public List getChildren() { return children; } } }