import java.io.File; import java.util.Arrays; import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.Scanner; import java.util.stream.Collectors; /** * https://www.hackerrank.com/contests/world-codesprint-12/challenges/red-knights-shortest-path */ public class RedKnightsShortestPath { class Position { int i, j; Position(int i, int j) { this.i = i; this.j = j; } @Override public String toString() { return String.format("(%d,%d)", i, j); } } enum Move { UL(-2, -1), UR(-2, 1), R(0, 2), LR(2, 1), LL(2, -1), L(0, -2); private final int i; private final int j; Move(int i, int j) { this.i = i; this.j = j; } } public static void main(String[] args) throws Exception { Scanner scanner = new Scanner(System.in); //Scanner scanner = new Scanner(new File("redKnightsShortestPath")); int n = scanner.nextInt(); int iStart = scanner.nextInt(); int jStart = scanner.nextInt(); int iEnd = scanner.nextInt(); int jEnd = scanner.nextInt(); RedKnightsShortestPath theSalesman = new RedKnightsShortestPath(n); List positions = theSalesman.shortestPath(iStart, jStart, iEnd, jEnd); if (positions == null) { System.out.println("Impossible"); } else { String path = positions.stream() .map(Move::toString) .collect(Collectors.joining(" ")); System.out.println(positions.size()); System.out.println(path); } } int n; Move[][] moves; Position[][] positions; public RedKnightsShortestPath(int n) { this.n = n; moves = new Move[n][n]; setPositions(); } private void setPositions() { positions = new Position[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { positions[i][j] = new Position(i, j); } } } /** * Run BFS from start position. * * @param iStart * @param jStart * @param iEnd * @param jEnd * @return the path from start to end if it exists, null if end is not reachable from start */ public List shortestPath(int iStart, int jStart, int iEnd, int jEnd) { Queue queue = new LinkedList<>(); Position start = positions[iStart][jStart]; queue.add(start); while (! queue.isEmpty()) { Position head = queue.remove(); for (Move move: nextMoves(head)) { Position neighbor = jump(head, move); if (moves[neighbor.i][neighbor.j] == null) { moves[neighbor.i][neighbor.j] = move; queue.add(neighbor); } } } Position end = positions[iEnd][jEnd]; return path(start, end); } private List path(Position start, Position end) { Move previousMove = moves[end.i][end.j]; if (previousMove == null) { return null; } List path = new LinkedList<>(); while (end != start) { path.add(0, previousMove); end = jumpReverse(end, previousMove); previousMove = moves[end.i][end.j]; } return path; } private List nextMoves(Position position) { return Arrays.stream(Move.values()) .filter(move -> isValid(position, move)) .collect(Collectors.toList()); } private boolean isValid(Position start, Move move) { int i = start.i + move.i; int j = start.j + move.j; return 0 <= i && i < n && 0 <= j && j < n; } private Position jump(Position start, Move move) { return positions[start.i + move.i][start.j + move.j]; } private Position jumpReverse(Position end, Move move) { return positions[end.i - move.i][end.j - move.j]; } }