using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution { static void printRoute(int n, int i_start, int j_start, int i_end, int j_end, int inRowSteps){ if (i_start == i_end && j_start == j_end) return; int rowDiff = Math.Abs(i_start - i_end); int colDiff = Math.Abs(j_start - j_end); int freeSpace = rowDiff/2 - colDiff; if (i_start > i_end)// GO UP! { if ((freeSpace > 0 || j_start > j_end) && j_start != 0) { Console.Write("UL "); printRoute(n,i_start-2, j_start-1, i_end, j_end, inRowSteps); return; } Console.Write("UR "); printRoute(n,i_start-2, j_start+1, i_end, j_end, inRowSteps); return; } if (i_start == i_end)// SAME ROW { if (j_start < j_end) { Console.Write("R "); printRoute(n,i_start, j_start+2, i_end, j_end, inRowSteps); return; } Console.Write("L "); printRoute(n,i_start, j_start-2, i_end, j_end, inRowSteps); return; } //GO DOWN! if (inRowSteps > 0 && j_start < j_end) { Console.Write("R "); printRoute(n,i_start, j_start+2, i_end, j_end, inRowSteps-1); return; } if ((freeSpace > 0 || j_start < j_end) && j_start != n-1) { Console.Write("LR "); printRoute(n,i_start+2, j_start+1, i_end, j_end, inRowSteps); return; } Console.Write("LL "); printRoute(n,i_start+2, j_start-1, i_end, j_end, inRowSteps); return; } static void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { int rowDiff = Math.Abs(i_start - i_end); int colDiff = Math.Abs(j_start - j_end); if (rowDiff % 2 != 0 || colDiff % 2 != rowDiff/2%2) { Console.WriteLine("Impossible"); return; } // else: possible int inRowSteps = (colDiff - rowDiff/2)/2 > 0 ? (colDiff - rowDiff/2)/2 : 0; Console.WriteLine(rowDiff/2 + inRowSteps); printRoute(n, i_start, j_start, i_end, j_end, inRowSteps); } 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); } }