#!/bin/python3 import sys sys.setrecursionlimit(1000000) from copy import copy ALREADY_DONE = set() # X,Y : X : row vers le bas positif, Y : colonnes ver la droite positif MOVES = {(0, 2): 'R', (0, -2): 'L', (-2, 1): 'UR', (-2, -1): 'UL', (2, 1): 'LR', (2, -1): 'LL' } MOVES_ORDERED = [(-2, -1), (-2, 1), (0,2), (2,1), (2, -1), (0, -2)] def compute_new_pos(pos, delta): return (pos[0] + delta[0], pos[1] + delta[1]) def is_out(pos, n): return pos[0] < 0 or pos[0] >= n or pos[1] >= n or pos[1] < 0 class RK: def __init__(self, position, n, target, historic, already_done): self.position = position self.target = target self.historic = historic self.already_done = already_done self.n = n class RK_BFS(RK): def __init__(self, position, n, target, historic, already_done, count_rk,queue, all_pos): RK.__init__(self, position, n, target, historic, already_done) self.count_rk = count_rk self.queue = queue self.all_pos = all_pos + [position] def expand(self): self.count_rk += 1 for move in MOVES_ORDERED: tmp_pos = compute_new_pos(self.position, move) if tmp_pos == self.target: """SOLUTION_FOUND, BFS => BEST""" new_histo = self.historic.copy() + [MOVES[move]] print(str(len(new_histo))) print(' '.join(new_histo)) #print(' : '.join(map(lambda x : str(x),self.all_pos + [tmp_pos]))) sys.exit(0) elif not (is_out(tmp_pos, self.n)) and not (tmp_pos in self.already_done): #print(str(tmp_pos) + ' ' + str(self.n)) new_histo = self.historic.copy() + [MOVES[move]] self.count_rk += 1 self.already_done.update([tmp_pos]) rk_bfs = RK_BFS(tmp_pos, self.n, self.target, new_histo, self.already_done, self.count_rk, self.queue, self.all_pos) self.queue.append(rk_bfs) if len(self.queue) == 0 : print("Impossible") sys.exit(0) rk = self.queue.pop(0) rk.expand() self.count_rk -= 1 if (self.count_rk == 0): print("Impossible") sys.exit(0) def printShortestPath(n, i_start, j_start, i_end, j_end): # Print the distance along with the sequence of moves. if (i_start % 2 != i_end % 2): print("Impossible") sys.exit(0) already_done = set(tuple([i_start, j_start])) historic = [] queue = list() all_pos = list() bk = RK_BFS((i_start, j_start), n, (i_end, j_end), historic, already_done, 0, queue, all_pos) bk.expand() 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)