import java.util.*; public class Solution { public static class Position { public int x; public int y; public Move move; public Position(int x, int y, Move move) { this.x = x; this.y = y; this.move = move; } public Position copyAndMove(Move move) { return new Position(x + move.diff_x, y + move.diff_y, move); } public String toString() { return "Position(" + x + ", " + y + ", " + (move != null ? move.name : "null" ) + ")"; } } static enum Move { UPPER_LEFT(-1, -2, "UL"), UPPER_RIGHT (1, -2, "UR"), RIGHT (2, 0, "R"), LOWER_RIGHT (1, 2, "LR"), LOWER_LEFT (-1, 2, "LL"), LEFT (-2, 0, "L"), /** Impossible move */ IMPOSSIBLE (0, 0, "Impossible"); private final int diff_x; private final int diff_y; private final int dirX; private final int dirY; private final String name; Move(int diff_x, int diff_y, String name) { this.diff_x = diff_x; this.diff_y = diff_y; this.dirX = getDirection(diff_x); this.dirY = getDirection(diff_y); this.name = name; } public String toString() { return name; } } static private double calcDistance(Position current, Position end) { int x = end.x - current.x; int y = end.y - current.y; return Math.sqrt(x*x + y*y); } private static int getDirection(int start, int end) { return getDirection(end - start); } private static int getDirection(int diff) { if (diff > 0) return 1; else if (diff < 0) return -1; return 0; } public static Position findNextPosition(Position currentPosition, Position endPosition) { double currentDistance = calcDistance(currentPosition, endPosition); Move move; int dirX = getDirection(currentPosition.x, endPosition.x); int dirY = getDirection(currentPosition.y, endPosition.y); Position position; double distance; Move bestMove = null; Position bestPosition = null; for(int i=0; i