using System; using System.Collections.Generic; using System.IO; using System.Linq; using System.Text; class Solution { static void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { StringBuilder path = new StringBuilder(); int val = pSP(n, i_start, j_start, i_end, j_end, path, new List()); if (val != int.MaxValue) { Console.WriteLine(val); } Console.WriteLine(pathL); } static int minMoves = int.MaxValue; static string pathL = "Impossible"; static int pSP(int n, int i_start, int j_start, int i_end, int j_end, StringBuilder path, List moves) { // Reached the end if (i_start == i_end && j_start == j_end) { if (minMoves > moves.Count) { minMoves = moves.Count; pathL = path.ToString(); } return 0; } // Impossible move if (i_start < 0 || j_start < 0 || i_start >= n || j_start >= n) { return int.MaxValue; } // Check if we are back in a square we've already been if (moves.Contains(i_start+" "+j_start)) { return int.MaxValue; } // Add position to list of moves var newMoves = new List(moves); newMoves.Add(i_start + " " + j_start); var ulsb = new StringBuilder(path.ToString()); ulsb.Append("UL "); var ursb = new StringBuilder(path.ToString()); ursb.Append("UR "); var rsb = new StringBuilder(path.ToString()); rsb.Append("R "); var lrsb = new StringBuilder(path.ToString()); lrsb.Append("LR "); var llsb = new StringBuilder(path.ToString()); llsb.Append("LL "); var lsb = new StringBuilder(path.ToString()); lsb.Append("L "); int ul = pSP(n, i_start - 2, j_start - 1, i_end, j_end, ulsb, newMoves); int ur = pSP(n, i_start - 2, j_start + 1, i_end, j_end, ursb, newMoves); int r = pSP(n, i_start, j_start + 2, i_end, j_end, rsb, newMoves); int lr = pSP(n, i_start + 2, j_start + 1, i_end, j_end, lrsb, newMoves); int ll = pSP(n, i_start + 2, j_start - 1, i_end, j_end, llsb, newMoves); int l = pSP(n, i_start, j_start - 2, i_end, j_end, lsb, newMoves); List all = new List { ul, ur, r, lr, ll, l }; List sblst = new List() { ulsb, ursb, rsb, lrsb, llsb, lsb }; var min = all.Min(); var sb = sblst[all.IndexOf(min)]; path.Append(sb.ToString()); return min == int.MaxValue ? min : 1 + min; } 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); } }