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[][] solutions = new int[n-1][n-1]; for (int i = 0; i < solutions.length; i++) { for (int j = 0; j < solutions.length; j++) { if (solutions[i][j] == 0) { // Needs to be solved: -1, or > 0 indicates a solution has already been found for j, i int solution = findSolution(n, i+1, j+1); solutions[i][j] = solution; // Update the solution for the reciprocal j, i element solutions[j][i] = solution; } } } for (int i = 0; i < solutions.length; i++) { for (int j = 0; j < solutions.length-1; j++) { System.out.print(solutions[i][j] + " "); } System.out.println(solutions[i][solutions.length-1]); } } private static int findSolution(int dimension, int move, int perpMove) { // Initialise a "board" so we can see which squares have already been landed on int[][] board = new int[dimension][dimension]; for (int i = 0; i < dimension; i++) { for (int j = 0; j < dimension; j++) { board[i][j] = -1; } } int currentx = 0, currenty = 0, moves = 0; return getLeastMoves(move, perpMove, currentx, currenty, moves, board); } private static int getLeastMoves(int movea, int moveb, int currentx, int currenty, int moves, int[][] board) { if (currentx == board.length-1 && currenty == board[0].length-1) { // Got to the end - return the moves board[currentx][currenty] = moves; return moves; } // Else, keep going if we're still on the board if (currentx >= 0 && currentx < board.length && currenty >= 0 && currenty < board.length) { // Only continue if our position hasn't already been reached with a fewer number of moves if (board[currentx][currenty] == -1 || board[currentx][currenty] > moves) { board[currentx][currenty] = moves; int leastMoves = -1; for (int i = -1; i <= 1; i+=2) { for (int j = -1; j <= 1; j+=2) { int newMove1 = getLeastMoves(movea, moveb, currentx+(movea*i), currenty+(moveb*j), moves+1, board); if (newMove1 == -1 || leastMoves == -1) { leastMoves = Math.max(leastMoves, newMove1); } else { leastMoves = Math.min(leastMoves, newMove1); } int newMove2 = getLeastMoves(movea, moveb, currentx+(moveb*j), currenty+(movea*i), moves+1, board); if (newMove2 == -1 || leastMoves == -1) { leastMoves = Math.max(leastMoves, newMove2); } else { leastMoves = Math.min(leastMoves, newMove2); } } } return leastMoves; } else { // Another route got here quicker, this branch is duff return -1; } } else { // Off the board, return -1 return -1; } } }