#!/bin/python3 import sys moves_delta = { "UL" : (-2, -1), "UR" : (-2, +1), "R" : (0, +2), "LR" : (+2, +1), "LL" : (+2, -1), "L" : (0, -2) } final_path = [] chosen_path = [] chosen_path_codes = [] final_path_codes = [] other_solution_moves = [] min_solution_len = sys.maxsize # OK def is_pair_already_included(new_pair, pairs): new_p_i, new_p_j = new_pair for pair in pairs: p_i, p_j = pair if p_i == new_p_i and p_j == new_p_j: # print("Pair included:" + str(new_p_i) + "," + str(new_p_j) + " " + str(pairs)) return True # print("Pair not included:" + str(new_p_i) + "," + str(new_p_j) + " " + str(pairs)) return False def is_same_move_in_other_solution(code, i, j): for move in other_solution_moves: s_i, s_j, s_code = move if i == s_i and j == s_j and code == s_code: return True return False # OK def is_good_move(code, i, j): d_i, d_j = moves_delta[code] new_i = i + d_i new_j = j + d_j new_pair = (new_i, new_j) is_good_move = (0 <= new_i < n) and (0 <= new_j < n) and (not is_pair_already_included(new_pair, chosen_path)) and (not is_same_move_in_other_solution(code, i, j)) return is_good_move # OK def get_next_move_codes(i, j): next_move_codes = [] #print("Key order:") codes = ["UL", "UR", "R", "LR", "LL", "L"] for x in range(len(codes)): #print(code, end=" ") code = codes[x] if is_good_move(code, i, j): next_move_codes.append(code) #print("Key order end \n") return next_move_codes def find_shortest_path(i, j, i_end, j_end, n): global min_solution_len global final_path global final_path_codes global chosen_path global chosen_path_codes global other_solution_moves # print(i, j, min_solution_len) if i == i_end and j == j_end: if len(chosen_path) < min_solution_len: min_solution_len = len(chosen_path) final_path = chosen_path[:] final_path_codes = chosen_path_codes[:] for k in range(0, len(final_path)): final_path_i, final_path_j = final_path[k] other_solution_moves.append((final_path_i, final_path_j, final_path_codes[k])) return for code in get_next_move_codes(i, j): # print(code + " " + str(len(chosen_path))) d_i, d_j = moves_delta[code] new_move = (i + d_i, j + d_j) chosen_path.append(new_move) chosen_path_codes.append(code) find_shortest_path(new_move[0], new_move[1], i_end, j_end, n) chosen_path = chosen_path[:-1] chosen_path_codes = chosen_path_codes[:-1] # OK def printShortestPath(n, i_start, j_start, i_end, j_end): # Print the distance along with the sequence of moves. find_shortest_path(i_start, j_start, i_end, j_end, n) if len(final_path_codes) > 0: print(len(final_path_codes)) print(' '.join(final_path_codes)) if len(final_path_codes) > 0 else print("Impossible") # for p_i, p_j in final_path: # print(p_i, p_j) # OK 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)