/* * To change this license header, choose License Headers in Project Properties. * To change this template file, choose Tools | Templates * and open the template in the editor. */ /** * * @author Aman deep */ import java.util.*; import java.io.*; public class KnightLonAChessBoard { static int n; public static void main(String[] args) { Scanner scan = new Scanner(System.in); n = scan.nextInt(); for(int i=1;i queue = new LinkedList(); queue.add(new Pair(0,0)); while(!queue.isEmpty()) { Pair p = queue.poll(); int x = p.x; int y = p.y; if(x-a>=0) { if(y-b>=0) if(!visited[x-a][y-b]) { visited[x-a][y-b]= true; min[x-a][y-b] = 1+min[x][y]; queue.add(new Pair(x-a,y-b)); } if(y+b=0) { if(!visited[x+a][y-b]) { visited[x+a][y-b] = true; min[x+a][y-b] = 1+min[x][y]; queue.add(new Pair(x+a,y-b)); } } if(y+b=0) { if(!visited[x+b][y-a]) { visited[x+b][y-a] = true; min[x+b][y-a] = 1+min[x][y]; queue.add(new Pair(x+b,y-a)); } } } if(x-b>=0) { if(y+a=0) { if(!visited[x-b][y-a]) { visited[x-b][y-a] = true; min[x-b][y-a] = 1+min[x][y]; queue.add(new Pair(x-b,y-a)); } } } } return min[n-1][n-1]; } static class Pair { int x,y; Pair(int x,int y) { this.x = x; this.y = y; } } }