#!/bin/python3 import sys from queue import Queue class RedKnight(): def __init__(self, n, start_x, start_y, goal_x, goal_y): self.x = start_x self.y = start_y self.target_x = goal_x self.target_y = goal_y self.n = n self.board = [[-1]*n] self.explored = set() self.queue = Queue() self.dist = [[-1]*n for _ in range(n)] self.prev = [[None]*n for _ in range(n)] def get_letter(self, i, j, prev_i, prev_j): if i - prev_i == -2 and j - prev_j == -1: return 'UL' if i - prev_i == -2 and j - prev_j == 1: return 'UR' if i - prev_i == 0 and j - prev_j == 2: return 'R' if i - prev_i == 2 and j - prev_j == 1: return 'LR' if i - prev_i == 2 and j - prev_j == -1: return 'LL' if i - prev_i == 0 and j - prev_j == -2: return 'L' def reverse(self): i, j = self.target_x, self.target_y result = '' while (i,j) != (self.x, self.y): prev_i, prev_j = self.prev[i][j] result = self.get_letter(i, j, prev_i, prev_j) + ' ' + result i, j = prev_i, prev_j return result def check(self, i, j): if (i, j) in self.explored: return False if i < 0 or j < 0 or i >= n or j >= n: return False return True def neighbors(self, node): i, j = node neighbors_list = [] ul_i, ul_j = i-2, j-1 if self.check(ul_i, ul_j): neighbors_list.append((ul_i, ul_j)) ur_i, ur_j = i-2, j+1 if self.check(ur_i, ur_j): neighbors_list.append((ur_i, ur_j)) r_i, r_j = i, j+2 if self.check(r_i, r_j): neighbors_list.append((r_i, r_j)) lr_i, lr_j = i+2, j+1 if self.check(lr_i, lr_j): neighbors_list.append((lr_i, lr_j)) ll_i, ll_j = i+2, j-1 if self.check(ll_i, ll_j): neighbors_list.append((ll_i, ll_j)) l_i, l_j = i, j-2 if self.check(l_i, l_j): neighbors_list.append((l_i, l_j)) return neighbors_list def start(self): self.queue.put((self.x, self.y)) self.dist[self.x][self.y] = 0 while not self.queue.empty(): node = self.queue.get() if node == (self.target_x, self.target_y): return self.dist[self.target_x][self.target_y] for neighbor in self.neighbors(node): n_i, n_j = neighbor i, j = node if self.dist[n_i][n_j] == -1: self.queue.put(neighbor) self.dist[n_i][n_j] = self.dist[i][j] + 1 self.prev[n_i][n_j] = i, j self.explored.add(node) return None def printShortestPath(n, i_start, j_start, i_end, j_end): # Print the distance along with the sequence of moves. # UL, UR, R, LR, LL, L knight = RedKnight(n, i_start, j_start, i_end, j_end) res = knight.start() if res is None: print('Impossible') else: print(res) print(knight.reverse()) if __name__ == "__main__": n = int(input().strip()) i_start, j_start, i_end, j_end = input().strip().split(' ') i_start, j_start, i_end, j_end = [int(i_start), int(j_start), int(i_end), int(j_end)] printShortestPath(n, i_start, j_start, i_end, j_end)