import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; import java.util.LinkedList; import java.util.Queue; public class Solution { private static final int BLANK = -1; private static int rowLen; private static int colLen; private static ArrayList Path = new ArrayList(); private static Queue queue; private static Coordinate[][] p; public static int path(int[][] board, int startRow, int startCol, int endRow, int endCol) { queue = new LinkedList(); queue.add(new Coordinate(startRow, startCol, "Origin")); queue.add(null); board[startRow][startCol] = 0; int hops=0; ArrayList check = new ArrayList(); p = new Coordinate[board.length][board.length]; // Base Case p[startRow][startCol] = new Coordinate(startRow, startCol, "Origin"); while (!queue.isEmpty()) { Coordinate popedItem = queue.poll(); if (popedItem == null && queue.peek() != null) { hops++; queue.offer(null); // for break in level continue; } if (popedItem == null && queue.peek() == null) { return -1; } int r = popedItem.row; int c = popedItem.col; board[r][c] = hops; if(r==endRow && c==endCol) { return hops; } Coordinate[] points = validCoordinates(board, r, c); // r, c: parents int flag = 0; for (Coordinate o : points) { if (o != null) { for (int i=0; i= 0 && row < colLen && col >= 0 && col < rowLen && board[row][col] == BLANK) return true; return false; } public static Coordinate[] validCoordinates(int[][] board, int row, int col) { Coordinate[] points = new Coordinate[6]; //UL if (isValid(board, row - 2, col - 1)) points[0] = new Coordinate(row - 2, col - 1, "UL"); // UR if (isValid(board, row - 2, col + 1)) points[1] = new Coordinate(row - 2, col + 1, "UR"); //R if (isValid(board, row , col + 2)) points[2] = new Coordinate(row , col + 2, "R"); //LR if (isValid(board, row + 2, col + 1)) points[3] = new Coordinate(row + 2, col + 1, "LR"); //LL if (isValid(board, row + 2, col - 1)) points[4] = new Coordinate(row + 2, col - 1, "LL"); //L if (isValid(board, row, col - 2)) points[5] = new Coordinate(row, col - 2, "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(); int[][] board = new int[n][n]; for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[i].length; j++) board[i][j] = BLANK; } rowLen = board.length; colLen = board[0].length; int hops=path(board, i_start, j_start, i_end, j_end ); if (hops == -1) System.out.println("Impossible"); else { System.out.println(hops); int i = i_end; int j = j_end; // Start from Destination while (i != i_start || j != j_start) { Path.add(p[i][j].dir); int r = p[i][j].row; int c = p[i][j].col; i = r; j = c; } for (int k=Path.size()-1; k >= 0; k--) { if (k==0) System.out.print(Path.get(k)); else System.out.print(Path.get(k) + " "); } } in.close(); } } class Coordinate implements Comparable { public int row; public int col; public String dir; public Coordinate() { row = 0; col = 0; } public Coordinate(int row, int col, String dir) { this.row = row; this.col = col; this.dir = dir; } @Override public int compareTo(Coordinate that) { return this.row - that.row - this.col - that.col; } }