#!/bin/python3 import sys def printShortestPath(n, i_start, j_start, i_end, j_end): # Print the distance along with the sequence of moves. find_path(n, tuple([i_start, j_start]), tuple([i_end, j_end])) def find_path(matrix_size, start_point, finish_point): possible_moves = [ tuple([-2, -1, 'UL']), tuple([-2, 1, 'UR']), tuple([0, 2, 'R']), tuple([2, 1, 'LR']), tuple([2, -1, 'LL']), tuple([0, -2, 'L']) ] track_path = [[0 for i in range(matrix_size)] for j in range(matrix_size)] steps = [] final_steps = [] track_path[start_point[0]][start_point[1]] = 1 if not is_safe_point(start_point, track_path): print('Impossible') return if not is_safe_point(finish_point, track_path): print('Impossible') return backtracking(start_point, finish_point, track_path, steps, possible_moves, final_steps) if len(final_steps) > 0: print(len(final_steps)) for i in range(len(final_steps)): print(final_steps[i], end=' ') else: print('Impossible') def backtracking(start_point, finish_point, track_path, steps, possible_moves, final_steps) -> bool: if start_point == finish_point: if len(final_steps) == 0 or len(steps) < len(final_steps): final_steps.clear() for i in range(len(steps)): final_steps.append(steps[i]) return True flag = False for i in range(len(possible_moves)): new_point = tuple([start_point[0] + possible_moves[i][0], start_point[1] + possible_moves[i][1]]) if not is_safe_point(new_point, track_path) or \ (len(steps) + 1 >= len(final_steps) and len(final_steps) > 0): continue steps.append(possible_moves[i][2]) track_path[new_point[0]][new_point[1]] = 1 if backtracking(new_point, finish_point, track_path, steps, possible_moves, final_steps) \ and not flag: flag = True steps.pop() track_path[new_point[0]][new_point[1]] = 0 if not flag: track_path[start_point[0]][start_point[1]] = 1 return False def is_safe_point(point, track_path) -> bool: if point[0] < len(track_path) and point[0] >= 0 \ and point[1] < len(track_path) and point[1] >= 0 \ and track_path[point[0]][point[1]] == 0: return True return False 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)