#!/bin/python3 import sys def printShortestPath(n, i_start, j_start, i_end, j_end): # Print the distance along with the sequence of moves. # x,y direction map based on moves dir_map = {"UL":(-1,-2), "UR":(1,-2), "R":( 2,0), "LL":(-1, 2), "LR":(1, 2), "L":(-2,0)} # function that gives the next spot on board based on current postition and direction next_posd = lambda xy,d: (xy[0]+dir_map[d][0], xy[1]+dir_map[d][1], d) # the order prescribed to achieve unique result path_order = ["UL", "UR", "R", "LR", "LL", "L"] # lets make sure we cannot visit start position again # via all the possible directions all_starts = [(j_start,i_start,d)[:2] for d in path_order] visited = set() goal = (j_end,i_end) """ path = [] # for debug depth = 1 # wont give shortest def dfs(curd, p, depth): nonlocal n, dir_map, goal, path_order, visited print("".join(["="]*depth), curd) print("".join([" "]*depth), visited) print("".join([" "]*depth), n, curd[0] < 0, curd[0] > n, curd[1] < 0, curd[1] > n) # if outside board just return if (curd[0] < 0 or curd[0] >= n or curd[1] < 0 or curd[1] >= n): print("off board",curd) return False if (curd[0],curd[1]) == goal: print("reached goal",) return True visited.add(curd[:2]) for d in path_order: next_curd = next_posd(curd[:2],d) if next_curd[:2] not in visited: if dfs(next_curd, p, depth+1): p += [next_curd] return True return False dfs(all_starts[0], path, 0) """ # bfs q = [all_starts[0]] # enqueu->append, dequeu->pop(0) reached_goal = False goal_node = None reverse_path = {} while len(q) > 0: curd = q.pop(0) if reached_goal: # print("reached goal") break if (curd[0],curd[1]) == goal: # print("reached goal") goal_node = curd break for d in path_order: next_curd = next_posd(curd[:2],d) if (next_curd[0] >= 0 and next_curd[0] < n and next_curd[1] >= 0 and next_curd[1] < n): if next_curd[:2] not in visited: q.append(next_curd) visited.add(next_curd[:2]) reverse_path[next_curd] = curd if (next_curd[0],next_curd[1]) == goal: reached_goal = True goal_node = next_curd break if goal_node is None: print("Impossible") return # rebuilding path cur = goal_node # print(cur,reverse_path) path = [] while cur != all_starts[0]: path += [cur[2]] cur = reverse_path[cur] print(len(path)) print(*path[::-1]) 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)