using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution { struct Cell { public int n_moves; public int prev_i; public int prev_j; public string move; } static void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { // Print the distance along with the sequence of moves. Cell[,] board = new Cell[n, n]; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) board[i, j].n_moves = -1; board[i_start, j_start].n_moves = 0; Queue que = new Queue(); que.Enqueue(i_start * n + j_start); bool possible = false; while (que.Count > 0) { int x = que.Dequeue(); int i_x = x / n; int j_x = x % n; if (i_x == i_end && j_x == j_end) { possible = true; break; } if (i_x > 1 && j_x > 0 && board[i_x - 2, j_x - 1].n_moves == -1) { board[i_x - 2, j_x - 1].n_moves = board[i_x, j_x].n_moves + 1; board[i_x - 2, j_x - 1].prev_i = i_x; board[i_x - 2, j_x - 1].prev_j = j_x; board[i_x - 2, j_x - 1].move = "UL"; que.Enqueue((i_x - 2) * n + (j_x - 1)); } if (i_x > 1 && j_x < n - 1 && board[i_x - 2, j_x + 1].n_moves == -1) { board[i_x - 2, j_x + 1].n_moves = board[i_x, j_x].n_moves + 1; board[i_x - 2, j_x + 1].prev_i = i_x; board[i_x - 2, j_x + 1].prev_j = j_x; board[i_x - 2, j_x + 1].move = "UR"; que.Enqueue((i_x - 2) * n + (j_x + 1)); } if (j_x < n - 2 && board[i_x, j_x + 2].n_moves == -1) { board[i_x, j_x + 2].n_moves = board[i_x, j_x].n_moves + 1; board[i_x, j_x + 2].prev_i = i_x; board[i_x, j_x + 2].prev_j = j_x; board[i_x, j_x + 2].move = "R"; que.Enqueue(i_x * n + (j_x + 2)); } if (i_x < n - 2 && j_x < n - 1 && board[i_x + 2, j_x + 1].n_moves == -1) { board[i_x + 2, j_x + 1].n_moves = board[i_x, j_x].n_moves + 1; board[i_x + 2, j_x + 1].prev_i = i_x; board[i_x + 2, j_x + 1].prev_j = j_x; board[i_x + 2, j_x + 1].move = "LR"; que.Enqueue((i_x + 2) * n + (j_x + 1)); } if (i_x < n - 2 && j_x > 0 && board[i_x + 2, j_x - 1].n_moves == -1) { board[i_x + 2, j_x - 1].n_moves = board[i_x, j_x].n_moves + 1; board[i_x + 2, j_x - 1].prev_i = i_x; board[i_x + 2, j_x - 1].prev_j = j_x; board[i_x + 2, j_x - 1].move = "LL"; que.Enqueue((i_x + 2) * n + (j_x - 1)); } if (j_x > 1 && board[i_x, j_x - 2].n_moves == -1) { board[i_x, j_x - 2].n_moves = board[i_x, j_x].n_moves + 1; board[i_x, j_x - 2].prev_i = i_x; board[i_x, j_x - 2].prev_j = j_x; board[i_x, j_x - 2].move = "L"; que.Enqueue(i_x * n + (j_x - 2)); } } if (possible) { Console.WriteLine(board[i_end, j_end].n_moves); string[] path = new string[board[i_end, j_end].n_moves]; for (int i = path.Length - 1; i >= 0; i--) { path[i] = board[i_end, j_end].move; int ti = board[i_end, j_end].prev_i; int tj = board[i_end, j_end].prev_j; i_end = ti; j_end = tj; } Console.WriteLine(string.Join(" ", path)); } else { 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); } }