using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution { static void PrintShortestPath(int n, int iStart, int jStart, int iEnd, int jEnd) { Point.Top = n; Point.FinalX = iEnd; Point.FinalY = jEnd; var max = n * n; var points = new List {new Point(iStart, jStart)}; for (var i=0 ; i !points.Any(a => a.Length == p.Length && a.X == p.X && a.Y == p.Y)).ToList(); if (options?.Any() ?? false) { if (options.First().Length > max) { Console.WriteLine("Impossible"); return; } points.AddRange(options); var solution = points.FirstOrDefault(p => p.X == iEnd && p.Y == jEnd); if (solution != null) { solution.Print(); return; } } } Console.WriteLine("Impossible"); } class Point { public static int Top { get; set; } = 0; public static int FinalX { get; set;} = 0; public static int FinalY { get; set;} = 0; public Point(int x, int y, int length = 0, string path = "", List pathData = null) { X = x; Y = y; Length = length; Path = path; PathData = pathData ?? new List(); PathData.Add($"{x}.{y}"); Difference = CalculateDifference(X, Y); } public int CalculateDifference(int x, int y) { return Math.Abs(x - FinalX) + Math.Abs(y - FinalY); } public int X { get; set; } public int Y { get; set; } public string Path { get; set; } public int Length { get; set; } public int Difference {get; set;} public List PathData { get; set; } public Point UL() { var x = X - 2; var y = Y - 1; return IsValid(x, y) ? new Point(x, y, Length + 1, $"{Path} UL") : null; } public Point UR() { var x = X - 2; var y = Y + 1; return IsValid(x, y) ? new Point(x, y, Length + 1, $"{Path} UR") : null; } public Point R() { var x = X; var y = Y + 2; return IsValid(x, y) ? new Point(x, y, Length + 1, $"{Path} R") : null; } public Point LR() { var x = X + 2; var y = Y + 1; return IsValid(x, y) ? new Point(x, y, Length + 1, $"{Path} LR") : null; } public Point LL() { var x = X + 2; var y = Y - 1; return IsValid(x, y) ? new Point(x, y, Length + 1, $"{Path} LL") : null; } public Point L() { var x = X; var y = Y - 2; return IsValid(x, y) ? new Point(x, y, Length + 1, $"{Path} L") : null; } public List Next() { var list = new List { UL(), UR(), R(), LR(), LL(), L() }; list = list.Where(i => i != null).ToList(); return list.Any() ? list : null; } public bool IsValid(int x, int y) { var p = $"{x}.{y}"; var d = CalculateDifference(x, y); return x >= 0 && x < Top && y >= 0 && y < Top && PathData.All(a => p != a) && d <= Difference; } public void Print() { Console.WriteLine(Length); Console.WriteLine(Path.Trim()); } } static void Main(String[] args) { var n = Convert.ToInt32(Console.ReadLine()); var ijTokens = Console.ReadLine().Split(' '); var iStart = Convert.ToInt32(ijTokens[0]); var jStart = Convert.ToInt32(ijTokens[1]); var iEnd = Convert.ToInt32(ijTokens[2]); var jEnd = Convert.ToInt32(ijTokens[3]); PrintShortestPath(n, iStart, jStart, iEnd, jEnd); } }