using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution { class QItem { public int x,y,step; public QItem(int x, int y, int s) { this.x = x; this.y = y; step = s; } } static bool isInside(int x, int y, int n) { return x >= 0 && x < n && y >= 0 && y < n; } static void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { //UL, UR, R, LR, LL, L int[] xDir = new int[]{-2,-2,0,2,2,0}; int[] yDir = new int[]{-1,1,2,1,-1,-2}; string[] move = new string[]{"UL", "UR", "R", "LR", "LL", "L"}; var start = new QItem(i_end, j_end, 0); Queue q = new Queue(); q.Enqueue(start); int[,] map = new int[n,n]; map[start.x, start.y] = -1; while(q.Count > 0) { var next = q.Dequeue(); for(int i = 0; i < xDir.Length; i++) { int newX = next.x + xDir[i]; int newY = next.y + yDir[i]; if(!isInside(newX, newY, n)) continue; if(map[newX,newY] == 0) { map[newX,newY] = next.step + 1; //Console.WriteLine(newX + "," + newY + " = " + map[newX,newY]); var newQItem = new QItem(newX, newY, next.step + 1); q.Enqueue(newQItem); } } } if(map[i_start,j_start] == 0) { Console.WriteLine("Impossible") ; } else { List path = new List(); Console.WriteLine(map[i_start,j_start]); int x = i_start; int y = j_start; while(map[x,y] != -1) { for(int i = 0; i < xDir.Length; i++) { int newX = x + xDir[i]; int newY = y + yDir[i]; if(!isInside(newX, newY, n)) continue; if(map[newX,newY] == -1 || map[newX,newY] + 1 == map[x,y]) { path.Add(move[i]); x = newX; y = newY; break; } } } int size = path.Count; for(int i = 0; i < size -1; i++) Console.Write(path[i] + " "); Console.WriteLine(path[size-1]); } } 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); } }