using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution { static void Main(String[] args) { System.Text.StringBuilder sb = new System.Text.StringBuilder(); int n = Convert.ToInt32(Console.ReadLine()); // your code goes here int[,] ans = new int[n - 1, n - 1]; for (int i = 1; i < n; i++) { for(int j = i; j < n; j++) { //check steps L(i,j) //Console.WriteLine("L({0},{1})", i, j); ans[i - 1, j - 1] = GetSteps(n, i, j); ans[j - 1, i - 1] = ans[i - 1, j - 1]; //Console.WriteLine("GOAL STEP = {0}",ans[i - 1, j - 1]); } } for(int i = 1; i < n; i++) { for (int j = 1; j < n; j++) { sb.AppendFormat("{0} ", ans[i - 1, j - 1]); } sb.Remove(sb.Length - 1, 1); sb.AppendLine(); } Console.WriteLine(sb.ToString()); } static int GetSteps(int n,int i,int j) { int step = 0; bool flgGoal = false; HashSet hs = new HashSet(); List locsBefore = new List(); List locsAfter = new List(); if (i == 1 && j == 1) return n-1; hs.Add(101); locsAfter.Add(new Location(1, 1)); //search all move patterns while(true) { locsBefore = new List(locsAfter); locsAfter.Clear(); step++; //Console.WriteLine("Step {0}", step); foreach (Location l in locsBefore) { //Console.WriteLine("search from ({0},{1})", l.x,l.y); int bx, by; //1 +i +j bx = l.x + i; by = l.y + j; //is goal if (bx == n && by == n) { flgGoal = true; break; } if (1 <= bx && bx <= n && 1 <= by && by <= n && !hs.Contains(bx * 100 + by)) { locsAfter.Add(new Location(bx, by)); hs.Add(bx * 100 + by); //Console.WriteLine("can move ({0},{1})", bx, by); } //2 +i -j bx = l.x + i; by = l.y - j; //is goal if (bx == n && by == n) { flgGoal = true; break; } if (1 <= bx && bx <= n && 1 <= by && by <= n && !hs.Contains(bx * 100 + by)) { locsAfter.Add(new Location(bx, by)); hs.Add(bx * 100 + by); //Console.WriteLine("can move ({0},{1})", bx, by); } //3 -i +j bx = l.x - i; by = l.y + j; //is goal if (bx == n && by == n) { flgGoal = true; break; } if (1 <= bx && bx <= n && 1 <= by && by <= n && !hs.Contains(bx * 100 + by)) { locsAfter.Add(new Location(bx, by)); //Console.WriteLine("can move ({0},{1})", bx, by); hs.Add(bx * 100 + by); } //4 -i -j bx = l.x - i; by = l.y - j; //is goal if (bx == n && by == n) { flgGoal = true; break; } if (1 <= bx && bx <= n && 1 <= by && by <= n && !hs.Contains(bx * 100 + by)) { locsAfter.Add(new Location(bx, by)); hs.Add(bx * 100 + by); //Console.WriteLine("can move ({0},{1})", bx, by); } //5 +j +i bx = l.x + j; by = l.y + i; //is goal if (bx == n && by == n) { flgGoal = true; break; } if (1 <= bx && bx <= n && 1 <= by && by <= n && !hs.Contains(bx * 100 + by)) { locsAfter.Add(new Location(bx, by)); hs.Add(bx * 100 + by); //Console.WriteLine("can move ({0},{1})", bx, by); } //6 +j -i bx = l.x + j; by = l.y - i; //is goal if (bx == n && by == n) { flgGoal = true; break; } if (1 <= bx && bx <= n && 1 <= by && by <= n && !hs.Contains(bx * 100 + by)) { locsAfter.Add(new Location(bx, by)); hs.Add(bx * 100 + by); //Console.WriteLine("can move ({0},{1})", bx, by); } //7 -j +i bx = l.x - j; by = l.y + i; //is goal if (bx == n && by == n) { flgGoal = true; break; } if (1 <= bx && bx <= n && 1 <= by && by <= n && !hs.Contains(bx * 100 + by)) { locsAfter.Add(new Location(bx, by)); //Console.WriteLine("can move ({0},{1})", bx, by); hs.Add(bx * 100 + by); } //8 -j -i bx = l.x - j; by = l.y - i; //is goal if (bx == n && by == n) { flgGoal = true; break; } if (1 <= bx && bx <= n && 1 <= by && by <= n && !hs.Contains(bx * 100 + by)) { locsAfter.Add(new Location(bx, by)); hs.Add(bx * 100 + by); //Console.WriteLine("can move ({0},{1})", bx, by); } } if (flgGoal) return step; //can not goal if (locsAfter.Count == 0) return -1; } } class Location { public int x; public int y; public Location(int a,int b) { x = a; y = b; } } }