#!/bin/python3 import sys visited_states = set() actions_possible = [ (-2,-1), # UL (-2,1), # UR (0,-2), # L (0,2), # R (2,1), # LR (2,-1), # LL ] current_min_length = None def printShortestPath(n, i_start, j_start, i_end, j_end, moves): #print(i_start, j_start) if (i_start, j_start) in visited_states: return global possible_paths, current_min_length if i_start == i_end and j_start == j_end: possible_paths += [list(moves)] if current_min_length is None: current_min_length = len(moves) else: current_min_length = min([current_min_length, len(moves)]) return visited_states.add((i_start, j_start)) for action in actions_possible: i_current, j_current = i_start + action[0], j_start + action[1] if i_current < 0 or j_current < 0: continue if i_current > n or j_current > n: continue if current_min_length != None: if len(moves) + 1 > current_min_length: continue moves += [action] printShortestPath(n,i_current, j_current, i_end, j_end, moves) moves.pop() visited_states.remove((i_start, j_start)) 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)] global possible_paths possible_paths = [] printShortestPath(n, i_start, j_start, i_end, j_end, []) if len(possible_paths) == 0: print("Impossible") else: #print("paths:", possible_paths) lengths = map(lambda x: len(x), possible_paths) min_path_length = min(lengths) min_paths = list(filter(lambda x: len(x) == min_path_length, possible_paths)) print(min_path_length) final_path = "" for step in min_paths[0]: move_string = "" if step[0] > 0: move_string += "L" if step[0] < 0: move_string += "U" if step[1] > 0: move_string += "R" if step[1] < 0: move_string += "L" final_path += move_string + " " print(final_path)