import java.util.ArrayList; import java.util.Scanner; final class Pair{ int axis_x; int axis_y; Pair oldPair; Pair(int axis_x,int axis_y,Pair oldPair){ this.axis_x = axis_x; this.axis_y = axis_y; this.oldPair = oldPair; } } public class KnightLOnAChessboard { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[][] matrix = new int[n-1][n-1]; for(int i=0;i list = new ArrayList(); list.add(new Pair(0,0,null)); //System.out.println("entering function for:"+step_x +","+step_y); //printArrayList(list); Pair lastPair = null; while(list.size()>0){ //System.out.println("in while"); //printArrayList(list); Pair currentPair = list.get(0); //System.out.println("testing for:"+(currentPair.axis_x + step_x) +","+(currentPair.axis_y + step_y)); if(currentPair.axis_x + step_x < n && currentPair.axis_y + step_y < n){ if(matrix[currentPair.axis_x + step_x][currentPair.axis_y + step_y] ==0){ matrix[currentPair.axis_x + step_x][currentPair.axis_y + step_y] = 9; list.add(lastPair = new Pair(currentPair.axis_x + step_x,currentPair.axis_y + step_y,currentPair)); if(currentPair.axis_x + step_x == n-1 && currentPair.axis_y + step_y == n-1){ break; } } } //System.out.println("testing for:"+(currentPair.axis_x + step_y) +","+(currentPair.axis_y + step_x)); if(currentPair.axis_x + step_y < n && currentPair.axis_y + step_x < n){ if(matrix[currentPair.axis_x + step_y][currentPair.axis_y + step_x] ==0){ matrix[currentPair.axis_x + step_y][currentPair.axis_y + step_x] = 9; list.add(lastPair = new Pair(currentPair.axis_x + step_y,currentPair.axis_y + step_x,currentPair)); if(currentPair.axis_x + step_y == n-1 && currentPair.axis_y + step_x == n-1){ break; } } } //System.out.println("testing for:"+(currentPair.axis_x - step_x) +","+(currentPair.axis_y + step_y)); if(currentPair.axis_x - step_x >= 0 && currentPair.axis_y + step_y < n){ if(matrix[currentPair.axis_x - step_x][currentPair.axis_y + step_y] ==0){ matrix[currentPair.axis_x - step_x][currentPair.axis_y + step_y] = 9; list.add(lastPair = new Pair(currentPair.axis_x - step_x,currentPair.axis_y + step_y,currentPair)); if(currentPair.axis_x - step_x == n-1 && currentPair.axis_y + step_y == n-1){ break; } } } //System.out.println("testing for:"+(currentPair.axis_x - step_y) +","+(currentPair.axis_y + step_x )); if(currentPair.axis_x - step_y >= 0 && currentPair.axis_y + step_x < n){ if(matrix[currentPair.axis_x - step_y][currentPair.axis_y + step_x] ==0){ matrix[currentPair.axis_x - step_y][currentPair.axis_y + step_x] = 9; list.add(lastPair = new Pair(currentPair.axis_x - step_y,currentPair.axis_y + step_x,currentPair)); if(currentPair.axis_x - step_y == n-1 && currentPair.axis_y + step_x == n-1){ break; } } } //System.out.println("testing for:"+(currentPair.axis_x + step_x) +","+(currentPair.axis_y - step_y )); if(currentPair.axis_x + step_x = 0){ if(matrix[currentPair.axis_x + step_x][currentPair.axis_y - step_y] ==0){ matrix[currentPair.axis_x + step_x][currentPair.axis_y - step_y] = 9; list.add(lastPair = new Pair(currentPair.axis_x + step_x,currentPair.axis_y - step_y,currentPair)); if(currentPair.axis_x + step_x == n-1 && currentPair.axis_y - step_y == n-1){ break; } } } //System.out.println("testing for:"+(currentPair.axis_x + step_y) +","+(currentPair.axis_y - step_x )); if(currentPair.axis_x + step_y < n && currentPair.axis_y - step_x >= 0){ if(matrix[currentPair.axis_x + step_y][currentPair.axis_y - step_x] ==0){ matrix[currentPair.axis_x + step_y][currentPair.axis_y - step_x] = 9; list.add(lastPair = new Pair(currentPair.axis_x + step_y,currentPair.axis_y - step_x,currentPair)); if(currentPair.axis_x + step_y == n-1 && currentPair.axis_y - step_x == n-1){ break; } } } //System.out.println("testing for:"+(currentPair.axis_x - step_x) +","+(currentPair.axis_y - step_y )); if(currentPair.axis_x - step_x >= 0 && currentPair.axis_y - step_y >= 0){ if(matrix[currentPair.axis_x - step_x][currentPair.axis_y - step_y] ==0){ matrix[currentPair.axis_x - step_x][currentPair.axis_y - step_y] = 9; list.add(lastPair = new Pair(currentPair.axis_x - step_x,currentPair.axis_y - step_y,currentPair)); if(currentPair.axis_x - step_x == n-1 && currentPair.axis_y - step_y == n-1){ break; } } } //System.out.println("testing for:"+(currentPair.axis_x - step_y) +","+(currentPair.axis_y - step_x )); if(currentPair.axis_x - step_y >= 0 && currentPair.axis_y - step_x >= 0){ if(matrix[currentPair.axis_x - step_y][currentPair.axis_y - step_x] ==0){ matrix[currentPair.axis_x - step_y][currentPair.axis_y - step_x] = 9; list.add(lastPair = new Pair(currentPair.axis_x - step_y,currentPair.axis_y - step_x,currentPair)); if(currentPair.axis_x - step_y == n-1 && currentPair.axis_y - step_x == n-1){ break; } } } //printArrayList(list); list.remove(0); //printArrayList(list); } int steps = 0; if(lastPair.axis_x != n-1 || lastPair.axis_y != n-1 ){ return -1; /*} if(list.get(list.size()-1).axis_x != n-1 && list.get(list.size()-1).axis_y != n-1){ return -1;*/ }else{ Pair temp = list.get(list.size()-1); while( temp.oldPair != null){ //System.out.println("here"); steps++; temp = temp.oldPair; } } //System.out.println(steps); return steps; } public static void printMatrix(int[][] matrix){ for(int i=0;i list){ for(int i=0;i