import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; abstract class ChessPiece { //Given a starting position what are the valid co-ordinates a chess piece can move to next // //Assumes empty chess board with no other pieces // //Returns ArrayList of valid ChessCoordinates for next move of a chess piece public abstract ArrayList validMoves(ChessCoordinate startPosition); } class RedKnight extends ChessPiece { //order UL, UR, R, LR, LL, L public ArrayList validMoves(ChessCoordinate startPosition) { //Will build up list of valid co-ordinates for next move ArrayList validCoordiantes = new ArrayList(); int xMove = -1; int yMove = -2; if (ChessCoordinate.isValidCoordinate(startPosition.x + xMove, startPosition.y + yMove)) { validCoordiantes.add((new ChessCoordinate((startPosition.x + xMove),(startPosition.y + yMove), "UL"))); } xMove = 1; yMove = -2; if (ChessCoordinate.isValidCoordinate(startPosition.x + xMove, startPosition.y + yMove)) { validCoordiantes.add((new ChessCoordinate((startPosition.x + xMove),(startPosition.y + yMove), "UR"))); } xMove = 2; yMove = 0; if (ChessCoordinate.isValidCoordinate(startPosition.x + xMove, startPosition.y + yMove)) { validCoordiantes.add((new ChessCoordinate((startPosition.x + xMove),(startPosition.y + yMove), "R"))); } xMove = 1; yMove = 2; if (ChessCoordinate.isValidCoordinate(startPosition.x + xMove, startPosition.y + yMove)) { validCoordiantes.add((new ChessCoordinate((startPosition.x + xMove),(startPosition.y + yMove), "LR"))); } xMove = -1; yMove = 2; if (ChessCoordinate.isValidCoordinate(startPosition.x + xMove, startPosition.y + yMove)) { validCoordiantes.add((new ChessCoordinate((startPosition.x + xMove),(startPosition.y + yMove), "LL"))); } xMove = -2; yMove = 0; if (ChessCoordinate.isValidCoordinate(startPosition.x + xMove, startPosition.y + yMove)) { validCoordiantes.add((new ChessCoordinate((startPosition.x + xMove),(startPosition.y + yMove), "L"))); } return validCoordiantes; } } // ChessCoordinate provides an abstraction for valid chess position on a square chess board of square BOARD_SIZE // Can be setup using algebraic chess notation class ChessCoordinate { public String title = ""; public int x; //horizontal coordinate public int y; //vertical coordinate public static int BOARD_SIZE = 8; //size of one side of the square chessboard //Throws IllegalArgumentException if invalid co-ordinate range public ChessCoordinate(int xCoordinate, int yCoordinate) throws IllegalArgumentException { if (isValidCoordinate(xCoordinate,yCoordinate)) { x = xCoordinate; y = yCoordinate; } else { throw new IllegalArgumentException("Invalid position co-ordinate. Board size is: " + BOARD_SIZE + " by " + BOARD_SIZE); } } public ChessCoordinate(int xCoordinate, int yCoordinate, String title) throws IllegalArgumentException { if (isValidCoordinate(xCoordinate,yCoordinate)) { x = xCoordinate; y = yCoordinate; this.title = title; } else { throw new IllegalArgumentException("Invalid position co-ordinate. Board size is: " + BOARD_SIZE + " by " + BOARD_SIZE); } } //Is the coordinate a valid position on the defined board size public static boolean isValidCoordinate(int xCoordinate, int yCoordinate) { if (xCoordinate >= 0 && xCoordinate < BOARD_SIZE && yCoordinate >= 0 && yCoordinate < BOARD_SIZE) { return true; } else { return false; } } //When does one ChessCoordinate equal another ChessCoordinate //Required method to override for use with 'contains' in collections // //Returns boolean public boolean equals(Object other) { ChessCoordinate another = (ChessCoordinate)other; if (another.x == this.x && another.y == this.y) { return true; } else { return false; } } //Allows for storage of class in Hash based collections //Builds a unique int as the hashcode based on concatenating the string representation of each part of the coordinate // //Returns int that is unique for each ChessCoordinate public int hashCode() { String xString = String.valueOf(this.x); String yString = String.valueOf(this.y); String stringCoordinate = xString + yString; return Integer.parseInt(stringCoordinate); } //Return the algebraic notation of the object's chess co-ordinate public String toString() { return (title); } } //ChessShortestPath provides a solution to the shortest path between a starting position and end position for a knight chess piece class ChessShortestPath { public ChessCoordinate startPos; public ChessCoordinate endPos; public ChessPiece pieceType; public ChessShortestPath(ChessCoordinate start, ChessCoordinate end, ChessPiece piece) { startPos = start; endPos = end; pieceType = piece; } //Finds the shortest path between a start node and end node for a unweighted graph using Breadth First Search // //For Chess Shortest Path, the chess board is an unweighted graph where the current position of the knight is the visited node in Breadth First Search and the positions of the possible next moves are the adjacent nodes // //Prints out the shortest path in terms of the steps of the shortest path, excluding the starting position public void shortestPath() { //Keep track of visited nodes and the parents of visited nodes (for finding the shortest path) HashMap parentNode = new HashMap(); //Queue of nodes to visit Queue positionQueue = new LinkedList(); //intially add the starting node parentNode.put(startPos,null); positionQueue.add(startPos); ChessCoordinate currentPosition = positionQueue.peek(); //Breadth first search while (positionQueue.peek() != null) //check if anymore nodes to visit { currentPosition = positionQueue.poll(); if (currentPosition.equals(endPos)) { break; //we have reached the end position on the graph via the shortest path so stop searching } //otherwise get adjacent nodes (possible moves from current position for knight) ArrayList nextPositions = pieceType.validMoves(currentPosition); for (ChessCoordinate adjacentPosition : nextPositions) { //if this adjacent nodes is one that hasn't been visited add it to the queue //also keep track of the adjacent node's parent (the current node) if (!parentNode.containsKey(adjacentPosition)) { parentNode.put(adjacentPosition,currentPosition); positionQueue.add(adjacentPosition); } } } //traverse back from end position coordinate to start position using the parent map to get shortest path //build up string of shortest path at same time ChessCoordinate currentNode = endPos; //start at the end node String shortestPath = "";//currentPosition.toString(); currentNode = currentPosition; while (parentNode.get(currentNode) != null) //stop once we are at the start node { shortestPath = currentNode.toString() + " " + shortestPath; currentNode = parentNode.get(currentNode); } if (shortestPath.length() == 0) //When start position = end position { shortestPath = startPos.toString(); } //Print out the shortest path found, excluding start position and including end position System.out.println(shortestPath); } } public class Solution { 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. //order UL, UR, R, LR, LL, L if(i_start % 2 != i_end % 2){ System.out.println("Impossible"); return; } int heightDifference = Math.abs(i_start - i_end); int sideDifference = Math.abs(j_start - j_end); if(heightDifference % 4 == 0){ if(sideDifference % 2 == 1){ System.out.println("Impossible"); return; } } if(heightDifference % 4 == 2){ if(sideDifference % 2 == 0){ System.out.println("Impossible"); return; } } //order UL, UR, R, LR, LL, L String moveList = ""; int moves = heightDifference/2 + Math.abs(sideDifference/2 ==0 ? 0 : sideDifference/2-heightDifference/2 ); System.out.println(moves); ChessCoordinate.BOARD_SIZE = n; /* while(moves > 0){ if(j_end < j_start){ if(i_end <= i_start){ j_start -= 2; i_start -= 1; moveList = moveList + "UL " continue; }else{ j_start -= 2; i_start += 1; moveList = moveList + "UR " continue; }}else{ if() } int heightDifference2 = Math.abs(j_start - j_end); int sideDifference2 = Math.abs(i_start - i_end); }*/ try { //must catch checked exception for invalid co-ordinates arguments ChessShortestPath knightShortestPath = new ChessShortestPath(new ChessCoordinate(j_start, i_start), new ChessCoordinate(j_end, i_end), new RedKnight()); knightShortestPath.shortestPath(); } catch (IllegalArgumentException e) { System.out.println(e.getMessage()); } } 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(); } }