using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution { static void Main(String[] args) { int n = Convert.ToInt32(Console.ReadLine()); int[,] s = new int[n,n]; int[,] ans = new int[n-1,n-1]; for(int i = 0; i < n-1; i++) for(int j = 0; j < n-1; j++) ans[i,j] = -1; Queue Q = new Queue(); Node root = new Node(0,0); Node goal = new Node(n-1, n-1); root.parent = null; Q.Enqueue(root); for(int a = 1; a < n; a++) { for(int b = a; b < n; b++) {//Console.WriteLine("a,b="+a+","+b); //Console.Write("\n\nChanging a,b"); Q.Clear(); Q.Enqueue(root); Node current = null; s = new int[n,n]; while(Q.Count > 0) { current = Q.Dequeue(); if(current.i == goal.i && current.j == goal.j) { ans[a-1,b-1] = ans[b-1, a-1] = current.level; //Console.WriteLine("\nGoal reached for (" + (a-1)+","+(b-1) + ") "+ ans[a-1,b-1] + " " + current.level); break; } var neighbours = getValidNeighbours(current, goal, a, b); foreach(var neighbour in neighbours) { if(s[neighbour.i, neighbour.j] != 1) { s[neighbour.i, neighbour.j] = 1; neighbour.parent = current; neighbour.level = current.level+1; Q.Enqueue(neighbour); //Console.Write(neighbour); } } } /*Console.Write("Path "); while(current != null) { Console.Write(current + "<-"); current = current.parent; }*/ } } //Console.Write("\n"); for(int i = 0; i < n-1; i++) { for(int j = 0; j < n-1; j++) Console.Write(ans[i,j] + " "); Console.WriteLine(); } } public static List getValidNeighbours(Node current, Node goal, int a, int b) { List nodeList = new List(); int i, j, k, l; i = j = k = l = 0; for(int z=1; z < 3; z++) { i = current.i + a; j = current.j + b; k = current.i - a; l = current.j - b; //Console.Write("\nijkl="+i+j+k+l); if(isIJValid(i, j, goal)) nodeList.Add(new Node(i,j)); if(isIJValid(i, l, goal)) nodeList.Add(new Node(i,l)); if(isIJValid(k, j, goal)) nodeList.Add(new Node(k,j)); if(isIJValid(k, l, goal)) nodeList.Add(new Node(k,l)); int temp = a; a = b; b = temp; } //Console.WriteLine("\nPrinting NeighBours of "+current+" with a,b="+a+","+b); //foreach(var n in nodeList) // Console.Write(n); return nodeList; } public static bool isIJValid(int i, int j, Node goal) { return (i >= 0 && i <= goal.i && j >= 0 && j <= goal.j); } } public class Node { public int i; public int j; public Node parent = null; public int level = 0; public Node(int a, int b) { i = a; j = b; } public override string ToString() { return "("+i+","+j+","+level+")"; } }