import java.util.*; public class Solution { public static void minMoves(int size) { HashMap,Integer> prev = new HashMap,Integer>(); for (int i = 1; i < size; i++) { for (int j = 1; j < size; j++) { System.out.print(minMoves(size, i, j, prev) + " "); } System.out.println(); } } public static int minMoves(int size, int a, int b, HashMap prev) { //Check if minMoves already calculated HashSet s = new HashSet(); s.add(a); s.add(b); if (prev.containsKey(s)){ return (int) prev.get(s); } //Initialize grid of 0s int[][] grid = new int[size][size]; //BFS LinkedList toVisit = new LinkedList(); int[] start = {0, 0}; toVisit.add(start); while (!(toVisit.isEmpty())) { int[] cell = toVisit.remove(); ArrayList reachable = reachable(size, cell[0], cell[1], a, b); for (int[] next_cell : reachable) { //If next cell hasn't already been visited if (grid[next_cell[0]][next_cell[1]] == 0) { grid[next_cell[0]][next_cell[1]] = grid[cell[0]][cell[1]] + 1; toVisit.add(next_cell); } //If reached end cell, return path length if ((next_cell[0] == size-1) && (next_cell[1] == size-1)) { HashSet n = new HashSet(); n.add(a); n.add(b); prev.put(n, grid[size-1][size-1]); return grid[size-1][size-1]; } } } //If end cell hasn't been reached, return -1 if (grid[size-1][size-1] == 0) { HashSet n = new HashSet(); n.add(a); n.add(b); prev.put(n, -1); return -1; } HashSet n = new HashSet(); n.add(a); n.add(b); prev.put(n, grid[size-1][size-1]); return grid[size-1][size-1]; } public static ArrayList reachable(int size, int x, int y, int a, int b) { ArrayList children = new ArrayList(); for (int i = -1; i<2; i+=2) { for (int j = -1; j<2; j+=2) { int new_x = x + (i*a); int new_y = y + (j*b); int[] cell = {new_x, new_y}; if (isValid(size, cell)) { children.add(cell); } } } for (int i = -1; i<2; i+=2) { for (int j = -1; j<2; j+=2) { int new_x = x + (i*b); int new_y = y + (j*a); int[] cell = {new_x, new_y}; if (isValid(size, cell)) { children.add(cell); } } } return children; } public static boolean isValid(int size, int[] cell) { return ((cell[0]=0) && (cell[1] >=0)); } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); minMoves(n); } }