using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution { private static int[,] grid; private static int gridLength; private static Point startPoint; private static Point endPoint; private static List moves = new List(); private static Dictionary ValidMoves = new Dictionary() { {"UL",new Point(-2,-1)}, {"UR",new Point(-2,1)}, {"R" ,new Point(0,2)}, {"LR",new Point(2,1)}, {"LL",new Point(2,-1)}, {"L" ,new Point(0,-2)}, }; private static Dictionary> ValidPaths = new Dictionary>(); 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]); gridLength = n - 1; startPoint = new Point(i_start, j_start); endPoint = new Point(i_end, j_end); grid = new int[n, n]; printShortestPath( i_start, j_start); } static void printShortestPath(int i_start, int j_start) { PrintGrid(0, i_start, j_start); var leastMoves = grid[endPoint.PointX, endPoint.PointY]; if (leastMoves > 0) { foreach (var move in ValidMoves) { moves = new List(); GetValidPaths(move.Key, grid[startPoint.PointX, startPoint.PointY], startPoint.PointX + move.Value.PointX, startPoint.PointY + move.Value.PointY); ValidPaths.Add(move.Key, moves); } Console.WriteLine(--leastMoves); var result = ValidPaths.FirstOrDefault(_ => _.Value.Count == leastMoves).Value; foreach (var move in result) Console.Write(move + " "); } else Console.WriteLine("Impossible"); } private static void GetValidPaths(string direction, int currentValue, int x, int y) { if(moves.Count>= grid[endPoint.PointX, endPoint.PointY]-1) return; if (x > gridLength || x < 0 || y > gridLength || y < 0) return; if ((x != endPoint.PointX || y != endPoint.PointY) && grid[x, y] >= grid[endPoint.PointX, endPoint.PointY]) return; if (grid[x, y] != 0 && grid[x, y] > currentValue && grid[x, y]<= grid[endPoint.PointX, endPoint.PointY]) moves.Add(direction); else return; foreach (var move in ValidMoves) GetValidPaths(move.Key, grid[x, y], x + move.Value.PointX, y + move.Value.PointY); } private static void PrintGrid(int currentcounter, int currentX, int currentY) { currentcounter += 1; if (currentX > gridLength || currentX < 0 || currentY > gridLength || currentY < 0) return; if (grid[endPoint.PointX, endPoint.PointY] > 0 && grid[endPoint.PointX, endPoint.PointY] < currentcounter) return; if (grid[currentX, currentY] == 0 || grid[currentX, currentY] > currentcounter) grid[currentX, currentY] = currentcounter; else return; foreach (var validMove in ValidMoves) PrintGrid(grid[currentX, currentY], currentX + validMove.Value.PointX, currentY + validMove.Value.PointY); } class Point { public int PointX { get; set; } public int PointY { get; set; } public Point(int x, int y) { PointX = x; PointY = y; } } }