using System; using System.Collections.Generic; using System.IO; using System.Linq; using System.Text; class Solution { static void Main(String[] args) { int n = Convert.ToInt32(Console.ReadLine()); int[,] answers = new int[n,n]; for (int i = 1; i < n; ++i) { for (int j = 1; j < n; ++j) { int ix = i - 1; int jx = j - 1; if (answers[jx, ix] != 0) { answers[ix, jx] = answers[jx, ix]; } else { answers[ix, jx] = Compute(n, i, j); } } } for (int i = 0; i < n - 1; ++i) { StringBuilder sb = new StringBuilder(); bool first = true; for (int j = 0; j < n - 1; ++j) { if (!first) { sb.Append(" "); } first = false; sb.Append(answers[i, j]); } Console.WriteLine(sb.ToString()); } } static int Compute(int n, int i, int j) { int[,] distances = new int[n,n]; int[] xDelta = new int[8] { 1, 1, 1, 1, -1, -1, -1, -1 }; int[] yDelta = new int[8] { 1, 1, -1, -1, 1, 1, -1, -1 }; for (int q = 0; q < 8; ++q) { if (q % 2 == 0) { xDelta[q] *= i; yDelta[q] *= j; } else { xDelta[q] *= j; yDelta[q] *= i; } } Pos p = new Pos() { x = 0, y = 0 }; Stack stack = new Stack(); stack.Push(p); while (stack.Count > 0) { p = stack.Pop(); int totalMoves = distances[p.x, p.y] + 1; for (int q = 0; q < 8; ++q) { int newX = p.x + xDelta[q]; if (newX < 0 || newX >= n) { continue; } int newY = p.y + yDelta[q]; if (newY < 0 || newY >= n) { continue; } int oldMoves = distances[newX, newY]; if (oldMoves == 0) { oldMoves = int.MaxValue; } if (totalMoves < oldMoves) { distances[newX, newY] = totalMoves; Pos px = new Pos() { x = newX, y = newY }; stack.Push(px); } } } if (distances[n - 1, n - 1] == 0) { return -1; } else { return distances[n - 1, n - 1]; } } private struct Pos { public int x; public int y; } }