import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { static int bestScore = 0; private static enum Movement { UL(-2,-1), UR(-2,1), R(0,2), LR(2,1), LL(2,-1), L(0,-2); public int i =0; public int j = 0; Movement (int i, int j) { this.i = i; this.j = j; } }; //this method will give the distance from start point to end point public static int getDistance (int i, int j, int i_end, int j_end) { int distance = 0; distance = Math.abs(i - i_end) + Math.abs(j - j_end); return distance; } public static boolean isValidMovement (Movement mv, int i, int j, int n) { boolean isValid = false; int finalI = i + mv.i; int finalJ = j + mv.j; if (finalI >= 0 && finalI < n && finalJ >=0 && finalJ < n) { isValid = true; // System.out.println(mv + " is valid:" + finalI + "," + finalJ + "," + n); } return isValid; } public static Movement bestMove (int i, int j, int i_end, int j_end, int n) { Movement best = null; int shortestDistance = getDistance(i, j, i_end, j_end); for (Movement mv : Movement.values()) { if (isValidMovement(mv, i, j, n)) { int newI = i + mv.i; int newJ = j + mv.j; int distance = getDistance(newI , newJ, i_end, j_end); if (distance < shortestDistance) { shortestDistance = distance; best = mv; } } } return best; } 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. //i=row //j=colunm List movements = new ArrayList(); boolean impossible = false; bestScore = getDistance(i_start, j_start, i_end, j_end); while (bestScore > 0 && !impossible) { int score = 0; Movement mv = bestMove (i_start, j_start, i_end, j_end, n); // System.out.println("best " + mv); if (mv != null) { i_start = i_start + mv.i; j_start = j_start + mv.j; score = getDistance(i_start, j_start, i_end, j_end); if (score <= bestScore) { bestScore = score; movements.add(mv); } else { impossible = true; } } else { impossible = true; } } if (!impossible) { System.out.println(movements.size()); for (int i=0; i