#!/bin/python from collections import deque from math import hypot import heapq import sys def isValid(n, pos, visited): row, col = pos try: return row < n and col < n and row >=0 and col >= 0 and visited[row][col] == False except: return False def dist(x1,y1, x2,y2): return hypot(x2-x1, y2-y1) def isCloser(old, new, end): oldrow, oldcol, newrow, newcol, endrow, endcol = old[0], old[1], new[0], new[1], end[0], end[1] return dist(newrow, newcol, endrow, endcol) < dist(oldrow, oldcol, endrow, endcol) def printShortestPath(n, start, end): # UL, UR, R, LR, LL, L movesPivs = [] # if start row > end row, we want to go up if start[0] > end[0]: movesPivs.extend([((-2, -1), "UL"), ((-2, 1), "UR")]) elif start[0] < end[0]: #if start row < end row, we want to go down movesPivs.extend([((2, -1), "LR"), ((2, 1), "LL")]) if start[1] != end[1]: movesPivs.extend([((0, -2), "L"), ((0, 2), "R")]) minMoves = sys.maxsize minScoreVal = sys.maxsize priorities = {'UL' : 0, 'UR':1, 'R':2, 'LR':3, 'LL':4, 'L':5} visited = [[False] * n for i in range(n)] result = "" queue = [] heapq.heappush(queue, ((0, start, 0, "", visited))) while queue: s = heapq.heappop(queue) scoreVal, pos, moves, path, visited_s = s row, col = pos visited_s[row][col] = True if pos == end: minScoreVal = scoreVal result = path minMoves = min(moves, minMoves) continue for move, txt in movesPivs: newMove = (pos[0]+move[0], pos[1]+move[1]) if not isCloser(pos, newMove, end): continue if isValid(n, newMove, visited_s): if path: tpath = path +" " +txt else: tpath = txt t_scoreVal = priorities[txt] heapq.heappush(queue, ((t_scoreVal, newMove, moves + 1, tpath, visited_s))) if result == "": print("Impossible") return print(minMoves) print(result) 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))