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> movesToGoal1 = DetermineMoves(0, 0, i, j, goal, new List>()); List> movesToGoal2 = DetermineMoves(0, 0, -i, j, goal, new List>()); List> movesToGoal3 = DetermineMoves(0, 0, i, -j, goal, new List>()); List> movesToGoal4 = DetermineMoves(0, 0, -i, -j, goal, new List>()); List> movesToGoal11 = DetermineMoves(0, 0, j, i, goal, new List>()); List> movesToGoal21 = DetermineMoves(0, 0, -j, i, goal, new List>()); List> movesToGoal31 = DetermineMoves(0, 0, j, -i, goal, new List>()); List> movesToGoal41 = DetermineMoves(0, 0, -j, -i, goal, new List>()); var moveLists = new List>>(); 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> minMovesList = null; foreach (List> 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> DetermineMoves(int xStart, int yStart, int xMove, int yMove, int goal, List> moveList) { int x2 = xStart + xMove; int y2 = yStart + yMove; if (x2 < 0 || x2 > goal) { return null; } if (y2 < 0 || y2 > goal) { return null; } Tuple lastMove = new Tuple(x2, y2); Tuple lastMove2 = new Tuple(y2, x2); Tuple goalMove = new Tuple(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> movesToGoal1 = DetermineMoves(x2, y2, xMove, yMove, goal, CloneList(moveList)); List> movesToGoal2 = DetermineMoves(x2, y2, -xMove, yMove, goal, CloneList(moveList)); List> movesToGoal3 = DetermineMoves(x2, y2, xMove, -yMove, goal, CloneList(moveList)); List> movesToGoal4 = DetermineMoves(x2, y2, -xMove, -yMove, goal, CloneList(moveList)); List> movesToGoal11 = DetermineMoves(x2, y2, yMove, xMove, goal, CloneList(moveList)); List> movesToGoal21 = DetermineMoves(x2, y2, -yMove, xMove, goal, CloneList(moveList)); List> movesToGoal31 = DetermineMoves(x2, y2, yMove, -xMove, goal, CloneList(moveList)); List> movesToGoal41 = DetermineMoves(x2, y2, -yMove, -xMove, goal, CloneList(moveList)); var moveLists = new List>>(); 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> minMovesList = null; foreach (List> ml in moveLists) { if (ml != null) { if (minMovesList == null) { minMovesList = ml; } else if (minMovesList.Count() > ml.Count()) { minMovesList = ml; } } } return minMovesList; } public static List> CloneList(List> listToClone) { List> copied = new List>(); foreach (Tuple move in listToClone) { copied.Add(move); } return copied; } }