import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); // your code goes here int[][] num_moves = new int[n-1][n-1]; for(int i=0; i stack = new ArrayDeque(); int x = a; int y = b; int path = 1; Integer[] square = {x, y, path}; stack.add(square); grid[square[0]][square[1]] = 1; int path_min = n*n; while(stack.isEmpty()==false) { square = stack.remove(); x = square[0]; y = square[1]; path = square[2]; //grid[x][y] = 0; //System.out.println("\npop: " + x + " " + y); if ( x==n-1 && y==n-1 ) { if(path_min > path) { path_min = path; //System.out.println("\nnew min is: " + path_min); } } else { if(x-b>=0 && y-a>=0 && grid[x-b][y-a]!=1) { Integer[] square1 = {x - b,y - a,path+1}; stack.add(square1); grid[square1[0]][square1[1]] = 1; //System.out.println("push: " + square[0] + " " + square[1]); } if(x-a>=0 && y-b>=0 && grid[x-a][y-b]!=1) { Integer[] square2 = {x - a,y - b,path+1}; stack.add(square2); grid[square2[0]][square2[1]] = 1; //System.out.println("push: " + square[0] + " " + square[1]); } if(x-b>=0 && y+a<=n-1 && grid[x-b][y+a]!=1) { Integer[] square3 = {x - b,y + a,path+1}; stack.add(square3); grid[square3[0]][square3[1]] = 1; //System.out.println("push: " + square[0] + " " + square[1]); } if(x+a<=n-1 && y-b>=0 && grid[x+a][y-b]!=1) { Integer[] square4 = {x + a,y - b,path+1}; stack.add(square4); grid[square4[0]][square4[1]] = 1; //System.out.println("push: " + square[0] + " " + square[1]); } if(x-a>=0 && y+b<=n-1 && grid[x-a][y+b]!=1) { Integer[] square5 = {x - a,y + b,path+1}; stack.add(square5); grid[square5[0]][square5[1]] = 1; //System.out.println("push: " + square[0] + " " + square[1]); } if(x+b<=n-1 && y-a>=0 && grid[x+b][y-a]!=1) { Integer[] square6 = {x + b,y - a,path+1}; stack.add(square6); grid[square6[0]][square6[1]] = 1; //System.out.println("push: " + square[0] + " " + square[1]); } if(x+b<=n-1 && y+a<=n-1 && grid[x+b][y+a]!=1) { Integer[] square7 = {x + b,y + a,path+1}; stack.add(square7); grid[square7[0]][square7[1]] = 1; //System.out.println("push: " + square[0] + " " + square[1]); } if(x+a<=n-1 && y+b<=n-1 && grid[x+a][y+b]!=1) { Integer[] square8 = {x + a,y + b,path+1}; stack.add(square8); grid[square8[0]][square8[1]] = 1; //System.out.println("push: " + square[0] + " " + square[1]); } } /* Iterator temp = stack.iterator(); while( temp.hasNext() ) { Integer[] coordinates = temp.next(); System.out.print(coordinates[0] + "," + coordinates[1] + " " + coordinates[2] + " | "); }*/ } return (path_min==n*n) ? -1 : path_min; } }