using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution { static void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { if (Math.Abs(i_start - i_end) % 2 != 0) { Console.WriteLine("Impossible"); } else if ((Math.Abs(i_start - i_end) % 4 == 0 && Math.Abs(j_start - j_end) % 2 != 0) || (Math.Abs(i_start - i_end) % 4 != 0 && Math.Abs(j_start - j_end) % 2 == 0)) { Console.WriteLine("Impossible"); } else { Node[,] matrix = new Node[n, n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { matrix[i, j] = new Node(n, i, j); } } Queue queuedNodes = new Queue(); matrix[i_start, j_start].state = 1; matrix[i_start, j_start].d = 0; queuedNodes.Enqueue(matrix[i_start, j_start]); while (queuedNodes.Count > 0 && matrix[i_end, j_end].state == 0) { var currentNode = queuedNodes.Dequeue(); foreach (string key in currentNode.neighbours.Keys) { var neighbour = matrix[currentNode.neighbours[key].Item1, currentNode.neighbours[key].Item2]; if (neighbour.state == 0) { matrix[neighbour.i_value, neighbour.j_value].previousMove = key; matrix[neighbour.i_value, neighbour.j_value].state = 1; matrix[neighbour.i_value, neighbour.j_value].d = currentNode.d + 1; matrix[neighbour.i_value, neighbour.j_value].parent = currentNode; queuedNodes.Enqueue(matrix[neighbour.i_value, neighbour.j_value]); } } matrix[currentNode.i_value, currentNode.j_value].state = 2; } var kNode = matrix[i_end, j_end]; Console.WriteLine(kNode.d); var moveList = new List(); while (kNode.previousMove != "") { moveList.Insert(0, kNode.previousMove); kNode = kNode.parent; } var finalstring = moveList[0]; for (int i = 1; i < moveList.Count; i++) { finalstring += " " + moveList[i]; } Console.WriteLine(finalstring); } // Print the distance along with the sequence of moves. } static void Main(String[] args) { int n = Convert.ToInt32(Console.ReadLine()); string[] tokens_i_start = Console.ReadLine().Split(' '); int i_start = Convert.ToInt32(tokens_i_start[0]); int j_start = Convert.ToInt32(tokens_i_start[1]); int i_end = Convert.ToInt32(tokens_i_start[2]); int j_end = Convert.ToInt32(tokens_i_start[3]); printShortestPath(n, i_start, j_start, i_end, j_end); n = Convert.ToInt32(Console.ReadLine()); } } public class Node { public Dictionary> neighbours = new Dictionary>(); public int i_value; public int j_value; public int state; public int d; public Node parent; public string previousMove; public Node(int gridsize, int i, int j) { i_value = i; j_value = j; state = 0; d = int.MaxValue; parent = null; InitNeighbours(gridsize); previousMove = ""; } public void InitNeighbours(int gridsize) { if (checkBounds(gridsize, i_value - 2, j_value - 1)) { neighbours["UL"] = new Tuple(i_value - 2, j_value - 1); } if (checkBounds(gridsize, i_value - 2, j_value + 1)) { neighbours["UR"] = new Tuple(i_value - 2, j_value + 1); } if (checkBounds(gridsize, i_value, j_value + 2)) { neighbours["R"] = new Tuple(i_value, j_value + 2); } if (checkBounds(gridsize, i_value + 2, j_value + 1)) { neighbours["LR"] = new Tuple(i_value + 2, j_value + 1); } if (checkBounds(gridsize, i_value + 2, j_value - 1)) { neighbours["LL"] = new Tuple(i_value + 2, j_value - 1); } if (checkBounds(gridsize, i_value, j_value - 2)) { neighbours["L"] = new Tuple(i_value, j_value - 2); } } public bool checkBounds(int gridsize, int i, int j) { return (i < gridsize && j < gridsize && i >= 0 && j >= 0); } }