import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { static boolean[][] visited; static boolean printShortestPath(int n, int i_start, int j_start, int i_end, int j_end, int moves) { Queue nextMoves = new LinkedList(); nextMoves.offer(new Move(i_start, j_start, 0, null, null)); Move finalMove = null; while(!nextMoves.isEmpty()) { Move move = nextMoves.poll(); // System.out.println(move); visited[move.x][move.y] = true; if (move.x == i_end && move.y == j_end) { System.out.println(move.movesCount); finalMove = move; Move[] kur = new Move[move.movesCount]; for(int i = move.movesCount - 1; i>=0; i--) { kur[i] = move; move = move.previous; } for(Move ff : kur) { System.out.print(ff.move + " "); } break; } List possibleMoves = getPossibleMoves(n, move); for(Move asd : possibleMoves) { visited[asd.x][asd.y] = true; nextMoves.offer(asd); } } return finalMove != null; } // UL, UR, R, LR, LL, L static List getPossibleMoves(int n, Move previousMove) { List result = new ArrayList(); if(isValidMove(n,previousMove.x -2, previousMove.y-1)){ result.add(new Move(previousMove.x -2, previousMove.y-1,previousMove.movesCount + 1, previousMove, "UL")); } if(isValidMove(n,previousMove.x -2, previousMove.y+1)){ result.add(new Move(previousMove.x -2, previousMove.y+1,previousMove.movesCount + 1, previousMove, "UR")); } if(isValidMove(n,previousMove.x, previousMove.y+2)){ result.add(new Move(previousMove.x, previousMove.y+2,previousMove.movesCount + 1, previousMove, "R")); } if(isValidMove(n,previousMove.x + 2, previousMove.y+1)){ result.add(new Move(previousMove.x + 2, previousMove.y+1,previousMove.movesCount + 1, previousMove, "LR")); } if(isValidMove(n,previousMove.x + 2, previousMove.y-1)){ result.add(new Move(previousMove.x + 2, previousMove.y-1,previousMove.movesCount + 1, previousMove, "LL")); } if(isValidMove(n,previousMove.x, previousMove.y-2)){ result.add(new Move(previousMove.x, previousMove.y-2,previousMove.movesCount + 1, previousMove, "L")); } return result; } static boolean isValidMove(int n, int x, int y) { if(x>=0 && y>=0 && x