import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { private int n; private int[][] marks; public Solution(int n) { this.n = n; marks = new int[n][n]; } public int calculateMinSteps(int a, int b) { for (int[] mark : marks) { Arrays.fill(mark, Integer.MAX_VALUE); } calculateMinSteps(0, 0, a, b, 0); final int result = marks[n - 1][n - 1]; return result == Integer.MAX_VALUE ? -1: result; } private void calculateMinSteps(int currentX, int currentY, int a, int b, int steps) { if (currentX < 0 || currentY < 0 || currentX >= n || currentY >= n) { return; } if (marks[currentX][currentY] <= steps) { return; } marks[currentX][currentY] = steps; if (currentX == n - 1 && currentY == n - 1) { return; } calculateMinSteps(currentX + a, currentY + b, a, b, steps + 1); calculateMinSteps(currentX + a, currentY - b, a, b, steps + 1); calculateMinSteps(currentX - a, currentY + b, a, b, steps + 1); calculateMinSteps(currentX - a, currentY - b, a, b, steps + 1); // switch calculateMinSteps(currentX + b, currentY + a, a, b, steps + 1); calculateMinSteps(currentX + b, currentY - a, a, b, steps + 1); calculateMinSteps(currentX - b, currentY + a, a, b, steps + 1); calculateMinSteps(currentX - b, currentY - a, a, b, steps + 1); } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[][] result = new int[n - 1][n - 1]; // your code goes here Solution solver = new Solution(n); for (int i = 1; i < n; i++) { for (int j = i; j < n; j++) { int minMoves = solver.calculateMinSteps(i, j); result[i - 1][j - 1] = minMoves; result[j - 1][i - 1] = minMoves; } } for (int[] row : result) { for (int el : row) { System.out.print(String.format("%d ", el)); } System.out.println(); } } }