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[][] results = new int[n][n]; //loop over results array, calculating result for each cell. for (int i=0; i queue = new LinkedList(); Cell root = board.getCell(0,0); root.depth=0; queue.add(root); while(!queue.isEmpty()){ Cell next = queue.remove(); //System.out.println(next.x+" "+next.y+" "+next.depth); if(next.x == n-1 && next.y == n-1){ foundAtDepth = next.depth; break; } for(Cell cell: board.getAdjacentList(next)){ if(!cell.marked){ cell.depth = next.depth+1; cell.marked = true; queue.add(cell); } } } return foundAtDepth; } } class Board{ private Cell[][] cells; private int a, b; private int size; public Board(int size, int a, int b){ this.cells = new Cell[size][size]; this.a=a; this.b=b; this.size = size; //System.out.println("Created board for: "+a+" "+b); } public Cell getCell(int x, int y){ if(x>size-1 || y>size-1 || x<0 || y<0){ return null; } if(cells[x][y] == null){ cells[x][y] = new Cell(x, y); } return cells[x][y]; } public List getAdjacentList(Cell cell){ //TODO can be optimized by returning only unmarked cells (maybe in another version of method) ArrayList adjacents = new ArrayList(); Cell adjacent; if((adjacent = getCell(cell.x+a, cell.y+b)) != null) adjacents.add(adjacent); if((adjacent = getCell(cell.x-a, cell.y+b)) != null) adjacents.add(adjacent); if((adjacent = getCell(cell.x+a, cell.y-b)) != null) adjacents.add(adjacent); if((adjacent = getCell(cell.x-a, cell.y-b)) != null) adjacents.add(adjacent); if((adjacent = getCell(cell.y+a, cell.x+b)) != null) adjacents.add(adjacent); if((adjacent = getCell(cell.y-a, cell.x+b)) != null) adjacents.add(adjacent); if((adjacent = getCell(cell.y+a, cell.x-b)) != null) adjacents.add(adjacent); if((adjacent = getCell(cell.y-a, cell.x-b)) != null) adjacents.add(adjacent); return adjacents; } } class Cell{ public int x, y; public boolean marked; public int depth; public Cell(int x, int y){ this.x=x; this.y=y; } }