using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution { static int maxVal = 10000000; static int min8(int a, int b, int c, int d, int e, int f, int g, int h) { return Math.Min(a, Math.Min(b, Math.Min(c, Math.Min(d, Math.Min(e, Math.Min(f, Math.Min(g,h))))))); } static int FindMoves(int[][] board, int n, int currX, int currY, int a, int b) { if (currX >= n || currY >= n || currX < 0 || currY < 0 || board[currY][currX] == 1) return maxVal; //return a large number that will hopefully not ever be the smallest if (currX == n - 1 && currY == n - 1) return 0; //Mark the current cell as visited board[currY][currX] = 1; //Try going left and up var leftBUpA = 1 + FindMoves(board, n, currX - b, currY - a, a, b); var leftAUpB = 1 + FindMoves(board, n, currX - a, currY - b, a, b); //Try going right and up var rightBUpA = 1 + FindMoves(board, n, currX + b, currY - a, a, b); var rightAUpB = 1 + FindMoves(board, n, currX + a, currY - b, a, b); //Try going right and down var rightBDownA = 1 + FindMoves(board, n, currX + b, currY + a, a, b); var rightADownB = 1 + FindMoves(board, n, currX + a, currY + b, a, b); //Try going left and down var leftBDownA = 1 + FindMoves(board, n, currX - b, currY + a, a, b); var leftADownB = 1 + FindMoves(board, n, currX - a, currY + b, a, b); board[currY][currX] = 0; return min8(leftBUpA, leftAUpB, rightBUpA, rightAUpB, rightBDownA, rightADownB, leftBDownA, leftADownB); } static void printKnightMoves(int n) { for (var i = 1; i < n; i++) { for (var j = 1; j < n; j++) { var board = new int[n][]; for (var x = 0; x < n; x++) { board[x] = new int[n]; } var result = FindMoves(board, n, 0, 0, i, j); Console.Write((result < maxVal) ? result : -1); Console.Write(" "); } Console.WriteLine(); } } static void Main(String[] args) { int n = Convert.ToInt32(Console.ReadLine()); // your code goes here printKnightMoves(n); } }