import java.lang.reflect.Array; import java.util.*; class Solution { private int[][] A; private int[] y_coords = {-1, 1, 2, 1, -1, -2}; //to easily get the valid knight moves private int[] x_coords = {-2, -2, 0, 2, 2, 0}; private String[] moveNames = {"UL", "UR", "R", "LR", "LL", "L"}; private int Sx, Sy, Ex, Ey; Solution (int[][] chessBoard, int Startx, int Starty, int Endx, int Endy) { A = chessBoard; Sx = Startx; Sy = Starty; Ex = Endx; Ey = Endy; } private class KnightPath { public int coords[]; //current position of this path public int count; //how many moves this path has taken public ArrayList visited; //previously visited positions of this path public ArrayList moveNames; KnightPath(int[] coordinates, int traversal_count, ArrayList visited_positions, ArrayList mName) { coords = coordinates; count = traversal_count; visited = visited_positions; moveNames = mName; } } private ArrayList getMoves(KnightPath position) { //gets the valid moves from a position ArrayList moves = new ArrayList(); for (int i = 0; i < 6; i++) { int[] move = {position.coords[0] + x_coords[i], position.coords[1] + y_coords[i]}; if (isValid(move) && isUnvisited(position.visited, move)) { ArrayList new_visited = new ArrayList(position.visited); new_visited.add(position.coords); ArrayList moveName; if (position.moveNames != null) { moveName = new ArrayList(position.moveNames); } else { moveName = new ArrayList(); } moveName.add(moveNames[i]); moves.add(new KnightPath(move, position.count+1, new_visited, moveName)); } } return moves; } private boolean isUnvisited(ArrayList visited, int[] move) { //checks if a move is in visited boolean unvisited = true; for (int[] s : visited) { if (s[0] == move[0] && s[1] == move[1]) { unvisited = false; } } return unvisited; } private boolean isValid(int[] move) { //checks if this position is out of bounds or contains non-zero int x_coord = move[0]; int y_coord = move[1]; return (x_coord >= 0 && A.length > x_coord && y_coord >= 0 && A[0].length > y_coord && A[x_coord][y_coord] == 0); } private boolean isDestination(int[] move) { //checks if we have reached the opposite corner return (move[0] == Ex && move[1] == Ey); } public void solution() { //using a breadth-first search, gets the possible paths to the destination Queue q = new ArrayDeque(); ArrayList counts = new ArrayList(); HashMap wonKnights = new HashMap(); int[] origin = {Sx, Sy}; KnightPath start_position = new KnightPath(origin, 0, new ArrayList(), null); q.add(start_position); //enqueue the starting point while(!q.isEmpty()) { ArrayList moves = getMoves(q.remove()); //dequeue child moves one by one if (!moves.isEmpty()) { for (KnightPath move : moves) { if (isDestination(move.coords)) { counts.add(move.count); wonKnights.put(move.count, move); } else { q.add(move); //enqueue the child move if it's valid and not destination } } } } Collections.sort(counts); //get the minimum count, AKA the number of moves of fastest path Integer key = counts.get(0); System.out.println(wonKnights.get(key).count); Collections.reverse(wonKnights.get(key).moveNames); for (String name : wonKnights.get(key).moveNames) { System.out.print(name + " "); } } 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(); in.close(); int[][] A = new int[n][n]; new Solution(A, i_start, j_start, i_end, j_end).solution(); } }