using System; using System.Collections.Generic; using System.IO; using System.Linq; namespace HackerRank { class Solution { class Step { public int i; public int j; public int count; } static void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { var queue = new Queue(); queue.Enqueue(new Step() { i = i_start, j = j_start, count = 0 }); var visited = new bool[n, n]; var stepDescription = new string[n, n]; Step resultStep = null; while (queue.Count > 0) { var currentStep = queue.Dequeue(); if (currentStep.i == i_end && currentStep.j == j_end) { resultStep = currentStep; break; } if (currentStep.i - 2 >= 0 && currentStep.j - 1 >= 0 && !visited[currentStep.i - 2, currentStep.j - 1]) { queue.Enqueue(new Step() { i = currentStep.i - 2, j = currentStep.j - 1, count = currentStep.count + 1 }); visited[currentStep.i - 2, currentStep.j - 1] = true; stepDescription[currentStep.i - 2, currentStep.j - 1] = "UL"; } if (currentStep.i - 2 >= 0 && currentStep.j + 1 < n && !visited[currentStep.i - 2, currentStep.j + 1]) { queue.Enqueue(new Step() { i = currentStep.i - 2, j = currentStep.j + 1, count = currentStep.count + 1 }); visited[currentStep.i - 2, currentStep.j + 1] = true; stepDescription[currentStep.i - 2, currentStep.j + 1] = "UR"; } if (currentStep.j + 2 < n && !visited[currentStep.i, currentStep.j + 2]) { queue.Enqueue(new Step() { i = currentStep.i, j = currentStep.j + 2, count = currentStep.count + 1 }); visited[currentStep.i, currentStep.j + 2] = true; stepDescription[currentStep.i, currentStep.j + 2] = "R"; } if (currentStep.i + 2 < n && currentStep.j + 1 < n && !visited[currentStep.i + 2, currentStep.j + 1]) { queue.Enqueue(new Step() { i = currentStep.i + 2, j = currentStep.j + 1, count = currentStep.count + 1 }); visited[currentStep.i + 2, currentStep.j + 1] = true; stepDescription[currentStep.i + 2, currentStep.j + 1] = "LR"; } if (currentStep.i + 2 < n && currentStep.j - 1 >= 0 && !visited[currentStep.i + 2, currentStep.j - 1]) { queue.Enqueue(new Step() { i = currentStep.i + 2, j = currentStep.j - 1, count = currentStep.count + 1 }); visited[currentStep.i + 2, currentStep.j - 1] = true; stepDescription[currentStep.i + 2, currentStep.j - 1] = "LL"; } if (currentStep.j - 2 >= 0 && !visited[currentStep.i, currentStep.j - 2]) { queue.Enqueue(new Step() { i = currentStep.i, j = currentStep.j - 2, count = currentStep.count + 1 }); visited[currentStep.i, currentStep.j - 2] = true; stepDescription[currentStep.i, currentStep.j - 2] = "L"; } } if (resultStep == null) Console.WriteLine("Impossible"); else { var stack = new Stack(); int i = resultStep.i; int j = resultStep.j; while(i != i_start || j != j_start) { stack.Push(stepDescription[i, j]); if (stepDescription[i, j] == "UL") { i += 2; j += 1; } else if (stepDescription[i, j] == "UR") { i += 2; j -= 1; } else if (stepDescription[i, j] == "LL") { i -= 2; j += 1; } else if (stepDescription[i, j] == "LR") { i -= 2; j -= 1; } else if (stepDescription[i, j] == "L") { j += 2; } else { j -= 2; } } Console.WriteLine(resultStep.count); while (stack.Count > 1) { Console.Write(stack.Pop() + " "); } Console.WriteLine(stack.Pop()); } } 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); } } }