#!/bin/python3 import sys class Board: def __init__(self, n): self.data = [999] * (n * n) self.back = [999] * (n * n) self.n = n def get(self, i, j): if (i*self.n + j) > len(self.data): return 999 return self.data[i*self.n + j] def set(self, i, j, val): self.data[i*self.n + j] = val def getBackPath(self, i, j): if (i*self.n + j) > len(self.data): return 999 return self.back[i*self.n + j] def setBackPath(self, i, j, val): self.back[i*self.n + j] = val def markMove(board, step, move): if (n-1 >= move[0] >= 0) and (n-1 >= move[1] >= 0): if (step + 1 <= board.get(move[0], move[1])): board.set(move[0],move[1], step + 1) return move def markMoves(board, step, pos): UL = (pos[0]-2, pos[1]-1) UR = (pos[0]-2, pos[1]+1) R = (pos[0], pos[1]+2) LR = (pos[0]+2, pos[1]+1) LL = (pos[0]+2, pos[1]-1) L = (pos[0], pos[1]-2) available_moves = [] for move in [UL, UR, R, LR, LL, L]: res = markMove(board, step, move) if res: available_moves.append(res) return available_moves def fillBoard(n, i_start, j_start, i_end, j_end): board = Board(n) board.set(i_start, j_start, 0) arr = [(0, i_start,j_start)] while len(arr): pos = arr.pop(0) available_moves = markMoves(board, step=pos[0], pos=(pos[1], pos[2])) for i in available_moves: arr.append((pos[0]+1, i[0], i[1])) return board def fillBackBoard(board, i_start, j_start, i_end, j_end): arr = [(board.get(i_end, j_end), i_end, j_end)] board.setBackPath(i_end, j_end, board.get(i_end, j_end)) while len(arr): pos = arr.pop(0) available_moves = markBackMoves(board, step=pos[0], pos=(pos[1], pos[2])) for i in available_moves: arr.append((pos[0]-1, i[0], i[1])) def markBackMoves(board, step, pos): UL = (pos[0]-2, pos[1]-1) UR = (pos[0]-2, pos[1]+1) R = (pos[0], pos[1]+2) LR = (pos[0]+2, pos[1]+1) LL = (pos[0]+2, pos[1]-1) L = (pos[0], pos[1]-2) available_moves = [] for move in [UL, UR, R, LR, LL, L]: res = markBackMove(board, step, move) if res: available_moves.append(res) return available_moves def markBackMove(board, step, move): if (n-1 >= move[0] >= 0) and (n-1 >= move[1] >= 0): if (step - 1 == board.get(move[0], move[1])): board.setBackPath(move[0],move[1], step - 1) return move def printPath(board, i_start, j_start, i_end, j_end): path = [] steps = 0 pos = [i_start, j_start] fillBackBoard(board, i_start, j_start, i_end, j_end) # print(pos) # print(board.back) last_run = False # while (pos[0] != i_end and pos[1] != j_end) or last_run: while True: # print(pos) # input() # Forward Ord: UL, UR, R, LR, LL, L # Back Order: LR, LL, L, UL, UR, R # UL = (pos[0]-2, pos[1]-1) # UR = (pos[0]-2, pos[1]+1) # R = (pos[0], pos[1]+2) # LR = (pos[0]+2, pos[1]+1) # LL = (pos[0]+2, pos[1]-1) # L = (pos[0], pos[1]-2) if board.getBackPath(pos[0]-2, pos[1]-1) == steps+1: path.append('UL') pos[0] -=2 pos[1] -= 1 steps += 1 continue if board.getBackPath(pos[0]-2, pos[1]+1) == steps+1: path.append('UR') pos[0] -= 2 pos[1] += 1 steps += 1 continue if board.getBackPath(pos[0], pos[1]+2) == steps+1: path.append('R') pos[1] += 2 steps += 1 continue if board.getBackPath(pos[0]+2, pos[1]+1) == steps+1: path.append('LR') pos[0] += 2 pos[1] += 1 steps += 1 continue if board.getBackPath(pos[0]+2, pos[1]-1) == steps+1: path.append('LL') pos[0] += 2 pos[1] -= 1 steps += 1 continue if board.getBackPath(pos[0], pos[1]-2) == steps+1: path.append('L') pos[1] -= 2 steps += 1 continue break print(" ".join(path)) def printShortestPath(n, i_start, j_start, i_end, j_end): board = fillBoard(n, i_start, j_start, i_end, j_end) result = board.get(i_end, j_end) if result == 999: print('Impossible') else: print(result) printPath(board, i_start, j_start, i_end, j_end) # Print the distance along with the sequence of 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)