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) { int[][] board = new int[n][n]; Point point = new Point(n, i_start, j_start, Movement.SS); LinkedList nextToVisit = new LinkedList(); HashMap parents = new HashMap(); int[][] visited = new int[n][n]; nextToVisit.add(point); visited[point.getX()][point.getY()] = 1; parents.put(point.getName(), null); Point[] points; while(!nextToVisit.isEmpty()) { point = nextToVisit.remove(); if (point == null) { continue; } board[point.getX()][point.getY()] = point.getValue(); if(point.getX()==i_end && point.getY()==j_end) { List shortestPath = new ArrayList<>(); Integer node = point.getName(); while(node != null) { shortestPath.add(node); node = parents.get(node); } shortestPath.remove(shortestPath.size()-1); Collections.reverse(shortestPath); printPath(board, n, shortestPath); return; } points = getPoints(board, n, point.getX(), point.getY()); for(Point p : points){ if(p != null && visited[p.getX()][p.getY()] == 0){ parents.put(p.getName(), point.getName()); nextToVisit.add(p); visited[p.getX()][p.getY()] = 1; } } } System.out.println("Impossible"); } static void printBoard(int[][] board, int n) { for(int i=0;i list) { int x, y; System.out.println(list.size()); for(Integer i : list) { y = i % n; x = i / n; System.out.print(Movement.fromInteger(board[x][y])+ " "); } } static boolean isValid(int[][] board, int n, int i, int j) { if(i >= 0 && j >= 0 && n > i && n > j && board[i][j] == 0) return true; return false; } static Point[] getPoints(int[][] board, int n, int i, int j){ Point[] points = new Point[6]; if(isValid(board,n,i-2, j-1)) points[0] = new Point(n, i-2, j-1, Movement.UL); if(isValid(board,n,i-2, j+1)) points[1] = new Point(n, i-2, j+1, Movement.UR); if(isValid(board,n,i, j+2)) points[2] = new Point(n, i, j+2, Movement.R); if(isValid(board,n, i+2, j+1)) points[3] = new Point(n, i+2, j+1, Movement.LR); if(isValid(board,n,i+2, j-1)) points[4] = new Point(n, i+2, j-1, Movement.LL); if(isValid(board,n,i, j-2)) points[5] = new Point(n, i, j-2, Movement.L); return points; } 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(); } } enum Movement{ SS, UL, UR, L, R, LL, LR; public static String fromInteger(int x) { switch(x) { case 0: return "SS"; case 1: return "UL"; case 2: return "UR"; case 3: return "L"; case 4: return "R"; case 5: return "LL"; case 6: return "LR"; } return null; } } class Point{ private Movement value; private int x; private int y; private int n ; public Point(int n, int x, int y, Movement value) { this.x = x; this.y = y; this.n = n; this.value = value; } public int getName() { return x * n + y; } public int getX() { return x; } public int getY() { return y; } public int getValue() { return value.ordinal(); } }