using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution { public class Board { private bool[] _visited; private int _n; public Board(int n) { _visited = new bool[n * n]; _n = n; } public void MarkVisited(int x, int y) { _visited[y * _n + x] = true; } public bool CanMoveTo(int x, int y) { return x >= 0 && y >= 0 && x < _n && y < _n && !_visited[y * _n + x]; } public Board Clone() { var b = new Board(_n); this._visited.CopyTo(b._visited, 0); return b; } } public class Move { public int dx; public int dy; public string Name; } static Move[] moves = new Move[] { new Move() { Name = "UL", dx = -1, dy = -2 }, new Move() { Name = "UR", dx = 1, dy = -2 }, new Move() { Name = "R", dx = 2, dy = 0 }, new Move() { Name = "LR", dx = 1, dy = 2 }, new Move() { Name = "LL", dx = -1, dy = 2 }, new Move() { Name = "L", dx = -2, dy = 0 } }; public class Context { public List Path; public Board Board; public int X; public int Y; } public static void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { Context start = new Context() { Board = new Board(n), X = j_start, Y = i_start, Path = new List() }; start.Board.MarkVisited(start.X, start.Y); List possibles = new List(); possibles.Add(start); while (possibles.Count > 0) { List nextLevelPossibles = new List(); foreach (var current in possibles) { foreach (var move in moves) { var nx = current.X + move.dx; var ny = current.Y + move.dy; if (current.Board.CanMoveTo(nx, ny)) { var next = new Context() { X = nx, Y = ny, Board = current.Board, Path = new List(current.Path) }; next.Board.MarkVisited(next.X, next.Y); next.Path.Add(move.Name); if (nx == j_end && ny == i_end) { System.Console.WriteLine(next.Path.Count); System.Console.WriteLine(string.Join(" ", next.Path)); return; } nextLevelPossibles.Add(next); } // ? prune? } } possibles = nextLevelPossibles; } System.Console.WriteLine("Impossible"); } 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); } }