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()); Compute(n); } private static void Compute(int n) { var output = new int[n, n]; for (var i = 1; i < n; ++i) { for (var j = 1; j < i; ++j) { Console.Write(output[i - 1, j - 1]); Console.Write(" "); } for (var j = i; j < n; ++j) { var result = Compute(i, j, n); output[i - 1, j - 1] = result; output[j - 1, i - 1] = result; Console.Write(result); if (j < n-1) { Console.Write(" "); } } Console.WriteLine(); } } public class Step:IComparable { public int Steps { get; set; } public Tuple Current { get; set; } public int CompareTo(Step other) { var compareTo = Steps.CompareTo(other.Steps); if (compareTo != 0) return compareTo; var compareToItem1 = Current.Item1.CompareTo(other.Current.Item1); if (compareToItem1 != 0) return compareToItem1; return Current.Item2.CompareTo(other.Current.Item2); } } private static int Compute(int i, int j, int n) { var table = new Step[n, n]; table[0, 0] = new Step {Steps = 0, Current = Tuple.Create(0,0)}; var sortedSet = new SortedSet {table[0, 0]}; while (sortedSet.Count > 0) { var thisCell = sortedSet.Min; sortedSet.Remove(thisCell); var current = thisCell.Current; foreach (var p in NextSteps(current, i, j, n)) { if (p.Item1 == n - 1 && p.Item2 == n - 1) return thisCell.Steps + 1; var newPos = table[p.Item1, p.Item2]; var stepsToHere = table[current.Item1, current.Item2].Steps; if (newPos == null || newPos.Steps > stepsToHere + 1) { var newStep = new Step {Current= p, Steps = stepsToHere + 1}; table[p.Item1, p.Item2] = newStep; sortedSet.Add(newStep); } } } return -1; } private static IEnumerable> NextSteps(Tuple current,int i ,int j, int n) { var x = current.Item1; var y = current.Item2; if (Valid(x + i, y + j, n)) yield return Tuple.Create(x + i, y + j); if (Valid(x + i, y - j, n)) yield return Tuple.Create(x + i, y - j); if (Valid(x - i, y + j, n)) yield return Tuple.Create(x - i, y + j); if (Valid(x - i, y - j, n)) yield return Tuple.Create(x - i, y - j); if (Valid(x + j, y + i, n)) yield return Tuple.Create(x + j, y + i); if (Valid(x + j, y - i, n)) yield return Tuple.Create(x + j, y - i); if (Valid(x - j, y + i, n)) yield return Tuple.Create(x - j, y + i); if (Valid(x - j, y - i, n)) yield return Tuple.Create(x - j, y - i); } private static bool Valid(int i, int j, int n) { return i >= 0 && j >= 0 && i < n && j < n; } }