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(); Knight knight = new Knight(n);// your code goes here knight.printResultGrid(); } } class Knight { private int gridSize; int[][] resultGrid; Knight (int size) { this.gridSize = size; createResultGrid(); start(); } private int getMaxSize() { return gridSize; } void createResultGrid () { this.resultGrid = new int[getMaxSize()-1][getMaxSize()-1]; for (int x = 0; x < getMaxSize()-1; x++) { for (int y = 0; y < getMaxSize()-1; y++) { //System.out.println("Creating: (" + x + ", " + y + ")" ); this.resultGrid[x][y] = -1; } } } void printResultGrid() { for (int x = 0; x < getMaxSize()-1; x++) { for (int y = 0; y < getMaxSize()-1; y++) { //System.out.println("Creating: (" + x + ", " + y + ")" ); System.out.print(this.resultGrid[x][y] + " "); } System.out.println(); } } private void start() { int posX = this.getMaxSize() - 1; int posY = this.getMaxSize() - 1; Pos pos = new Pos(posX, posY); for (int a = 1; a < getMaxSize(); a++) { for (int b = 1; b < getMaxSize(); b++) { this.resultGrid[a-1][b-1] = knightL(a, b, pos); } } //System.out.println(knightL(4, 4, pos)); } private int knightL(int a, int b, Pos pos) { Set passed = new HashSet<>(); passed.add(pos); Set allMoves = new HashSet(); allMoves.addAll(pos.checkNextValidMoves(a, b, this.gridSize)); if(allMoves.contains(new Pos(0, 0))) { return 1; } boolean notFound = true; int count = -1; while (notFound) { count++; Set nextMoves = new HashSet<>(); for (Pos p: allMoves) { nextMoves.addAll(p.checkNextValidMoves(a, b, this.gridSize)); } if (allMoves.isEmpty()) { notFound = false; count = -1; } passed.addAll(allMoves); if(nextMoves.contains(new Pos(0, 0))) { count += 2; notFound = false; } nextMoves.removeAll(passed); allMoves = nextMoves; } return count; } } class Pos { int x; int y; List nextValidMoves; public Pos (int x, int y) { this.x = x; this.y = y; } public List checkNextValidMoves(int a, int b, int gridMax) { this.nextValidMoves = new ArrayList<>(); int xaRight = this.x + a; int xaLeft = this.x - a; int ybDown = this.y + b; int ybUp = this.y - b; int xbRight = this.x + b; int xbLeft = this.x - b; int yaDown = this.y + a; int yaUp = this.y - a; if (xaRight < gridMax){ if (ybDown < gridMax){ addValidMove(xaRight, ybDown); } if (ybUp > -1) { addValidMove(xaRight, ybUp); } } if (xaLeft > -1) { if (ybDown < gridMax){ addValidMove(xaLeft, ybDown); } if (ybUp > -1) { addValidMove(xaLeft, ybUp); } } if (xbRight < gridMax) { if (yaDown < gridMax){ addValidMove(xbRight, yaDown); } if (yaUp > -1) { addValidMove(xbRight, yaUp); } } if (xbLeft > -1) { if (yaDown < gridMax){ addValidMove(xbLeft, yaDown); } if (yaUp > -1) { addValidMove(xbLeft, yaUp); } } return this.nextValidMoves; } private void addValidMove(int x, int y) { Pos pos = new Pos(x, y); if (this.nextValidMoves.contains(pos)) { return; } this.nextValidMoves.add(pos); } @Override public boolean equals(Object o) { if (o == this) { return true; } if (!(o instanceof Pos)) { return false; } Pos p = (Pos) o; //System.out.println("this.x: " + this.x + " this.y: " + this.y ) ; //System.out.println("x: " + x + " y: " + y ) ; return this.x == p.x && this.y == p.y; } @Override public int hashCode() { return this.x; } }