import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static class Pair { private F first; // first member of pair private S second; // second member of pair public Pair(F first, S second) { this.first = first; this.second = second; } public void setFirst(F first) { this.first = first; } public void setSecond(S second) { this.second = second; } public F getFirst() { return first; } public S getSecond() { return second; } public String toString() { return "(" + first + "," + second + ")"; } } public static class Location { int numPaths; List tracks; public Location(int numPaths, List tracks) { this.numPaths = numPaths; this.tracks = tracks; } public String toString() { return "(numPaths: " + numPaths + " tracks: " + tracks + ')'; } } static Location[][] boards; static ArrayDeque> workQueue; public static int findMinPath(int n, int i, int j) { workQueue.add(new Pair<>(0, 0)); boards[0][0] = new Location(0, new ArrayList<>()); while (!workQueue.isEmpty()) { Pair loc = workQueue.remove(); Location currentLocation = boards[loc.first][loc.second]; // System.out.format("Loc %d,%d\n", loc.first, loc.second); List> newPairs = new ArrayList<>(); newPairs.add(new Pair<>(loc.first + i, loc.second + j)); newPairs.add(new Pair<>(loc.first + j, loc.second + i)); newPairs.add(new Pair<>(loc.first + i, loc.second - j)); newPairs.add(new Pair<>(loc.first - j, loc.second + i)); newPairs.add(new Pair<>(loc.first - i, loc.second + j)); newPairs.add(new Pair<>(loc.first + j, loc.second - i)); newPairs.add(new Pair<>(loc.first - i, loc.second - j)); newPairs.add(new Pair<>(loc.first - j, loc.second - i)); for (Pair newPair : newPairs) { if (newPair.first >= 0 && newPair.first < n && newPair.second >= 0 && newPair.second < n) { if (boards[newPair.first][newPair.second] == null) { workQueue.add(newPair); List newTracks = new ArrayList<>(currentLocation.tracks); newTracks.add(new Pair<>(loc.first, loc.second)); Location newLocation = new Location(currentLocation.numPaths + 1, newTracks); boards[newPair.first][newPair.second] = newLocation; // System.out.format("New Loc x:%d y:%d: %s\n", // newPair.first, newPair.second, newLocation); if (newPair.first == n - 1 && newPair.second == n - 1) { return newLocation.numPaths; } } } } } return -1; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[][] minPaths = new int[n][n]; boards = new Location[n][n]; workQueue = new ArrayDeque<>(); for (int i = 1; i < n; i++) { for (int j = 1; j < n; j++) { // System.out.format("---i:%d j:%d---\n", i, j); minPaths[i][j] = findMinPath(n, i, j); // System.out.format("***i:%d j:%d min:%d\n", i, j, // minPaths[i][j]); System.out.format("%d ", minPaths[i][j]); boards = new Location[n][n]; workQueue = new ArrayDeque<>(); } System.out.println(""); } } }