using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution { static void Main(String[] args) { int boardSize = Convert.ToInt32(Console.ReadLine()); // your code goes here int goal = boardSize - 1; for (int i = 1; i < boardSize; i++) { for (int j = 1; j < boardSize; j++) { List<Tuple<int, int>> movesToGoal1 = DetermineMoves(0, 0, i, j, goal, new List<Tuple<int, int>>()); List<Tuple<int, int>> movesToGoal2 = DetermineMoves(0, 0, -i, j, goal, new List<Tuple<int, int>>()); List<Tuple<int, int>> movesToGoal3 = DetermineMoves(0, 0, i, -j, goal, new List<Tuple<int, int>>()); List<Tuple<int, int>> movesToGoal4 = DetermineMoves(0, 0, -i, -j, goal, new List<Tuple<int, int>>()); List<Tuple<int, int>> movesToGoal11 = DetermineMoves(0, 0, j, i, goal, new List<Tuple<int, int>>()); List<Tuple<int, int>> movesToGoal21 = DetermineMoves(0, 0, -j, i, goal, new List<Tuple<int, int>>()); List<Tuple<int, int>> movesToGoal31 = DetermineMoves(0, 0, j, -i, goal, new List<Tuple<int, int>>()); List<Tuple<int, int>> movesToGoal41 = DetermineMoves(0, 0, -j, -i, goal, new List<Tuple<int, int>>()); var moveLists = new List<List<Tuple<int, int>>>(); if (movesToGoal1 != null) { moveLists.Add(movesToGoal1); } if (movesToGoal2 != null) { moveLists.Add(movesToGoal2); } if (movesToGoal3 != null) { moveLists.Add(movesToGoal3); } if (movesToGoal4 != null) { moveLists.Add(movesToGoal4); } if (movesToGoal11 != null) { moveLists.Add(movesToGoal11); } if (movesToGoal21 != null) { moveLists.Add(movesToGoal21); } if (movesToGoal31 != null) { moveLists.Add(movesToGoal31); } if (movesToGoal41 != null) { moveLists.Add(movesToGoal41); } List<Tuple<int, int>> minMovesList = null; foreach (List<Tuple<int, int>> moveList in moveLists) { if (moveList != null) { if (minMovesList == null) { minMovesList = moveList; } else if (minMovesList.Count() > moveList.Count()) { minMovesList = moveList; } } } int value = minMovesList == null ? -1 : minMovesList.Count(); Console.Write(value + " "); } Console.WriteLine(); } } public static List<Tuple<int, int>> DetermineMoves(int xStart, int yStart, int xMove, int yMove, int goal, List<Tuple<int, int>> moveList) { int x2 = xStart + xMove; int y2 = yStart + yMove; if (x2 < 0 || x2 > goal) { return null; } if (y2 < 0 || y2 > goal) { return null; } Tuple<int, int> lastMove = new Tuple<int, int>(x2, y2); Tuple<int, int> lastMove2 = new Tuple<int, int>(y2, x2); Tuple<int, int> goalMove = new Tuple<int, int>(goal, goal); if (moveList.Contains(lastMove) || moveList.Contains(lastMove2)) { //Dead end return null; } if (moveList.Contains(goalMove)) { return moveList; } moveList.Add(lastMove); if (x2 == goal && y2 == goal) { //Hit goal return moveList; } List<Tuple<int, int>> movesToGoal1 = DetermineMoves(x2, y2, xMove, yMove, goal, CloneList(moveList)); List<Tuple<int, int>> movesToGoal2 = DetermineMoves(x2, y2, -xMove, yMove, goal, CloneList(moveList)); List<Tuple<int, int>> movesToGoal3 = DetermineMoves(x2, y2, xMove, -yMove, goal, CloneList(moveList)); List<Tuple<int, int>> movesToGoal4 = DetermineMoves(x2, y2, -xMove, -yMove, goal, CloneList(moveList)); List<Tuple<int, int>> movesToGoal11 = DetermineMoves(x2, y2, yMove, xMove, goal, CloneList(moveList)); List<Tuple<int, int>> movesToGoal21 = DetermineMoves(x2, y2, -yMove, xMove, goal, CloneList(moveList)); List<Tuple<int, int>> movesToGoal31 = DetermineMoves(x2, y2, yMove, -xMove, goal, CloneList(moveList)); List<Tuple<int, int>> movesToGoal41 = DetermineMoves(x2, y2, -yMove, -xMove, goal, CloneList(moveList)); var moveLists = new List<List<Tuple<int, int>>>(); if (movesToGoal1 != null) { moveLists.Add(movesToGoal1); } if (movesToGoal2 != null) { moveLists.Add(movesToGoal2); } if (movesToGoal3 != null) { moveLists.Add(movesToGoal3); } if (movesToGoal4 != null) { moveLists.Add(movesToGoal4); } if (movesToGoal11 != null) { moveLists.Add(movesToGoal11); } if (movesToGoal21 != null) { moveLists.Add(movesToGoal21); } if (movesToGoal31 != null) { moveLists.Add(movesToGoal31); } if (movesToGoal41 != null) { moveLists.Add(movesToGoal41); } List<Tuple<int, int>> minMovesList = null; foreach (List<Tuple<int, int>> ml in moveLists) { if (ml != null) { if (minMovesList == null) { minMovesList = ml; } else if (minMovesList.Count() > ml.Count()) { minMovesList = ml; } } } return minMovesList; } public static List<Tuple<int, int>> CloneList(List<Tuple<int, int>> listToClone) { List<Tuple<int, int>> copied = new List<Tuple<int, int>>(); foreach (Tuple<int, int> move in listToClone) { copied.Add(move); } return copied; } }