using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution { static void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { int cantMov = 0; int menorCant = 0; List visitados = new List(); visitados.Add(i_start + "," + j_start); Dictionary movimientos = new Dictionary(); Dictionary mejorMovimientos = new Dictionary(); bool result = tablero(ref i_start, ref j_start, i_end, j_end, n, ref cantMov, ref menorCant, ref visitados, ref movimientos, ref mejorMovimientos); if (menorCant > 0) { Console.WriteLine(menorCant); string[] mov = new string[mejorMovimientos.Count]; int i = 0; foreach (var item in mejorMovimientos) { mov[i++] = item.Value; } Console.WriteLine(String.Join(" ", mov)); } else { Console.WriteLine("Impossible"); } } static bool tablero(ref int i_start, ref int j_start, int i_end, int j_end, int n, ref int cantMov, ref int menorCant, ref List visitados, ref Dictionary movimientos, ref Dictionary mejorMovimientos) { int tmpi = i_start; int tmpj = j_start; string inipos = visitados.First(); Dictionary movimientosTmp = new Dictionary(); foreach (var item in movimientos) { movimientosTmp.Add(item.Key, item.Value); } bool next = nextMov(ref i_start, ref j_start, i_end, j_end, n, ref cantMov, ref visitados, ref movimientos, mejorMovimientos); if (next == false) { visitados.Add("0"); if (movimientosTmp.Count > 0) { movimientos = movimientosTmp; string lastPos = movimientos.Last().Key; cantMov = movimientos.Count; movimientos.Remove(lastPos); cantMov--; if (cantMov == 0) { lastPos = visitados.First(); } else { lastPos = movimientos.Last().Key; } string[] pos = lastPos.Split(','); tmpi = int.Parse(pos[0]); tmpj = int.Parse(pos[1]); visitados.Add(lastPos); return tablero(ref tmpi, ref tmpj, i_end, j_end, n, ref cantMov, ref menorCant, ref visitados, ref movimientos, ref mejorMovimientos); } else { return false; } } else { string nextPos = movimientos.Last().Key; if (nextPos == i_end + "," + j_end) { visitados.Add("0"); if (menorCant == 0 || cantMov < menorCant) { menorCant = cantMov; mejorMovimientos = movimientos; if (mejorMovimientos.Count == 1) { return true; } } movimientos = movimientosTmp; string lastPos = movimientos.Last().Key; cantMov = movimientos.Count; movimientos.Remove(lastPos); cantMov--; if (cantMov == 0) { lastPos = visitados.First(); } else { lastPos = movimientos.Last().Key; } visitados.Add(lastPos); string[] pos = lastPos.Split(','); tmpi = int.Parse(pos[0]); tmpj = int.Parse(pos[1]); return tablero(ref tmpi, ref tmpj, i_end, j_end, n, ref cantMov, ref menorCant, ref visitados, ref movimientos, ref mejorMovimientos); } else { return tablero(ref i_start, ref j_start, i_end, j_end, n, ref cantMov, ref menorCant, ref visitados, ref movimientos, ref mejorMovimientos); } } } static bool nextMov(ref int i_start, ref int j_start, int i_end, int j_end, int n, ref int cantMov, ref List visitados, ref Dictionary movimientos, Dictionary mejorMovimientos) { string pref = ""; int prefi = -1; int prefj = -1; //UL int i = i_start - 2; int j = j_start - 1; if (i == i_end && j == j_end) { movimientos.Add(i + "," + j, "UL"); cantMov++; i_start = i; j_start = j; return true; } if (i >= 0 && i < n && j >= 0 && j < n && !movimientos.ContainsKey(i + "," + j)&&!(String.Join("-", visitados.ToArray()).Contains(i_start + "," + j_start + "-" + i + "," + j))&&!visitados.First().Equals(i + "," + j)) { pref = "UL"; prefi = i; prefj = j; } //UR i = i_start - 2; j = j_start + 1; if (i == i_end && j == j_end) { movimientos.Add(i + "," + j, "UR"); cantMov++; i_start = i; j_start = j; return true; } if (i >= 0 && i < n && j >= 0 && j < n && !movimientos.ContainsKey(i + "," + j) && pref.Equals("") && !(String.Join("-", visitados.ToArray()).Contains(i_start + "," + j_start + "-" + i + "," + j)) && !visitados.First().Equals(i + "," + j)) { pref = "UR"; prefi = i; prefj = j; } //R i = i_start; j = j_start + 2; if (i == i_end && j == j_end) { movimientos.Add(i + "," + j, "R"); cantMov++; i_start = i; j_start = j; return true; } if (i >= 0 && i < n && j >= 0 && j < n && !movimientos.ContainsKey(i + "," + j) && pref.Equals("") && !(String.Join("-", visitados.ToArray()).Contains(i_start + "," + j_start + "-" + i + "," + j)) && !visitados.First().Equals(i + "," + j)) { pref = "R"; prefi = i; prefj = j; } //LR i = i_start + 2; j = j_start + 1; if (i == i_end && j == j_end) { movimientos.Add(i + "," + j, "LR"); cantMov++; i_start = i; j_start = j; return true; } if (i >= 0 && i < n && j >= 0 && j < n && !movimientos.ContainsKey(i + "," + j) && pref.Equals("") && !(String.Join("-", visitados.ToArray()).Contains(i_start + "," + j_start + "-" + i + "," + j)) && !visitados.First().Equals(i + "," + j)) { pref = "LR"; prefi = i; prefj = j; } //LL i = i_start + 2; j = j_start - 1; if (i == i_end && j == j_end) { movimientos.Add(i + "," + j, "LL"); cantMov++; i_start = i; j_start = j; return true; } if (i >= 0 && i < n && j >= 0 && j < n && !movimientos.ContainsKey(i + "," + j) && pref.Equals("") && !(String.Join("-", visitados.ToArray()).Contains(i_start + "," + j_start + "-" + i + "," + j)) && !visitados.First().Equals(i + "," + j)) { pref = "LL"; prefi = i; prefj = j; } //L i = i_start; j = j_start - 2; if (i == i_end && j == j_end) { movimientos.Add(i + "," + j, "L"); cantMov++; i_start = i; j_start = j; return true; } if (i >= 0 && i < n && j >= 0 && j < n && pref.Equals("") && !movimientos.ContainsKey(i + "," + j) && !(String.Join("-", visitados.ToArray()).Contains(i_start + "," + j_start + "-" + i + "," + j)) && !visitados.First().Equals(i + "," + j)) { pref = "L"; prefi = i; prefj = j; } if (!pref.Equals("")) { movimientos.Add(prefi + "," + prefj, pref); visitados.Add(prefi + "," + prefj); cantMov++; i_start = prefi; j_start = prefj; return true; } return false; } 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); } }