#!/bin/python3 import sys from heapq import * def printShortestPath(n, i_start, j_start, i_end, j_end): # Print the distance along with the sequence of moves. # we use Dijkstra's algorithm, starting at the end node # lower number is more preferred move_pref = {"UL":1, "UR":2, "R":3, "LR":4, "LL":5, "L":6} visited_nodes = [] # elements are (row, col) to represent a cell cost_to_go = {} # key = (row, col), value = cost prev_node = {} # key = (row, col), value = [(row_prev, col_prev), move to get from current to prev] queue = [] cost_to_go[(i_end, j_end)] = 0 heappush(queue, [0, (i_end, j_end)]) start_reached = False while queue and not start_reached: current_node = heappop(queue) current_cost = current_node[0] current_node = current_node[1] visited_nodes.append(current_node) if current_node == (i_start, j_start): start_reached = True else: # find neighbour nodes neighbours = [] # note that the appended moves are OPPOSITES! # (i.e. we append the move to get from neighbour to current_node) if current_node[1]-2 >= 0: # L neighbours.append([(current_node[0], current_node[1]-2), "R"]) if current_node[1]+2 < n: # R neighbours.append([(current_node[0], current_node[1]+2), "L"]) if current_node[0]-2 >= 0 and current_node[1]-1 >= 0: # UL neighbours.append([(current_node[0]-2, current_node[1]-1), "LR"]) if current_node[0]-2 >= 0 and current_node[1]+1 < n: # UR neighbours.append([(current_node[0]-2, current_node[1]+1), "LL"]) if current_node[0]+2 < n and current_node[1]-1 >= 0: # LL neighbours.append([(current_node[0]+2, current_node[1]-1), "UR"]) if current_node[0]+2 < n and current_node[1]+1 < n: # LR neighbours.append([(current_node[0]+2, current_node[1]+1), "UL"]) # update costs to neighbour nodes for neighb in neighbours: if neighb[0] not in visited_nodes: if neighb[0] not in cost_to_go: cost_to_go[neighb[0]] = current_cost+1 heappush(queue, [current_cost+1, neighb[0]]) prev_node[neighb[0]] = [current_node, neighb[1]] # include the move elif current_cost+1 < cost_to_go[neighb[0]]: cost_to_go[neighb[0]] = current_cost+1 heappush(queue, [current_cost+1, neighb[0]]) prev_node[neighb[0]] = [current_node, neighb[1]] elif current_cost+1 == cost_to_go[neighb[0]]: # if the new move is of better priority if move_pref[neighb[1]] < move_pref[prev_node[neighb[0]][1]]: prev_node[neighb[0]] = [current_node, neighb[1]] if not start_reached: print("Impossible") else: # find and print the path on_node = (i_start, j_start) moves = [] while on_node != (i_end, j_end): moves.append(prev_node[on_node][1]) on_node = prev_node[on_node][0] print(len(moves)) print(" ".join(moves)) 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)