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 [][] cBoard = new int [n][n]; ArrayDeque dQX = new ArrayDeque(); ArrayDeque dQY = new ArrayDeque(); int mvCount = 0; int found= 0; for(int a= 1; a< n; a++){ for(int b=1; b 0){ mvCount = recursiveEvalNeighbor(dQX.poll(), dQY.poll(), cBoard, a, b, n, dQX, dQY); } System.out.print(mvCount + " "); } System.out.println(); } } public static int recursiveEvalNeighbor(int x, int y, int[][] cBoard, int a, int b, int n, ArrayDeque dQX, ArrayDeque dQY){ // System.out.println("x "+ (x+a) + " y "+ (y + b) + " n "+ n); int depth = cBoard[x][y]; boolean hasNeighbor = false; if(x+a <= (n-1) && y+b <= (n-1)){ if( x+a == n-1 && y+b == n-1){ dQX.clear(); dQY.clear(); return depth+1 ; } else if(cBoard[x+a][y+b]<=0){ hasNeighbor = true; dQX.addLast(x+a); dQY.addLast(y+b); cBoard[x+a][y+b] = depth+1; } } if(x - a >= 0 && y + b <= n-1){ if(cBoard[x-a][y+b]<=0){ hasNeighbor = true; dQX.addLast(x-a); dQY.addLast(y+b); cBoard[x-a][y+b] = depth+1; } } if(x + a <= n-1 && y - b > 0){ if(cBoard[x+a][y-b]<=0){ hasNeighbor = true; dQX.addLast(x+a); dQY.addLast(y-b); cBoard[x+a][y-b] = depth+1; } } if(x - a >= 0 && y -b >0 || x - a > 0 && y -b >= 0){ if(cBoard[x-a][y-b]<=0){ hasNeighbor = true; dQX.addLast(x-a); dQY.addLast(y-b); cBoard[x-a][y-b] = depth+1; } } //Switching a and b moves if(x + b <= n-1 && y +a <= n-1){ if( x + b == n-1 && y + a == n-1){ dQX.clear(); dQY.clear(); return depth+1 ; } else{ if(cBoard[x+b][y+a]<=0){ hasNeighbor = true; dQX.addLast(x+b); dQY.addLast(y+a); cBoard[x+b][y+a] = depth+1; } } } if(x - b >= 0 && y + a <= n-1){ if(cBoard[x-b][y+a]<=0){ hasNeighbor = true; dQX.addLast(x-b); dQY.addLast(y+a); cBoard[x-b][y+a] = depth+1; } } if(x+ b <= n-1 && y - a >= 0){ if(cBoard[x+b][y-a]<=0){ hasNeighbor = true; dQX.addLast(x+b); dQY.addLast(y-a); cBoard[x+b][y-a] = depth+1; } } if(x - b > 0 && y -a >0 ){ if(cBoard[x-b][y-a]<=0){ hasNeighbor = true; dQX.addLast(x-b); dQY.addLast(y-a); cBoard[x-b][y-a] = depth+1; } } //It has neighbor so make a move and increase move number by 1 if(hasNeighbor) { return recursiveEvalNeighbor(dQX.poll(), dQY.poll(), cBoard, a, b, n, dQX, dQY); } //If it has no neighbor then return -1 else{ //mvCount--; return -1; } } }