#!/bin/python3 import sys import math def printShortestPath(n, i_start, j_start, i_end, j_end): # Print the distance along with the sequence of moves. # First check if the Goal is reachable # Check if Goal is in valid row: if(i_end%2 == i_start%2): # Check some column properties of Goal # if the dist between columnGoal and column is even, both columnGoal and colKnight should be both even or odd if((j_end - j_start)%2 == 0): if(j_end%2 == j_start%2): findShortestPath(i_start, j_start, i_end, j_end) else: print("Impossible") # if the dist between them is odd, one needs to be odd while the other even else: if(j_end%2 != j_start%2): findShortestPath(i_start, j_start, i_end, j_end) else: print("Impossible") else: print("Impossible") def findShortestPath(i_start, j_start, i_end, j_end): # Since we know the Goal is reachable at this point, convert to a more convenient coord system # posKnight = [int(i_start/2), int(j_start/2)] # posGoal = [int(i_end/2), int(j_end/2)] # dictMoves = {'UL':(-1,-1),'UR':(0,-1),'R':(1,0),'LR':(0,1),'LL':(-1,1),'L':(-1,0)} posKnight = [i_start, j_start] posGoal = [i_end, j_end] dictMoves = {'UL':(-2,-1),'UR':(-2,1),'R':(0,2),'LR':(2,1),'LL':(2,-1),'L':(0,-2)} # Placeholder values bestDist = 100 bestMove = 'R' totDist = 0 finalPath = [] # Find the path! while(posKnight != posGoal): for key in dictMoves.items(): posDist = distFormula(posKnight[0] + key[1][0], posKnight[1] + key[1][1], posGoal[0], posGoal[1]) if(posDist < bestDist): bestMove = key[0] bestDist = posDist finalPath.append(bestMove) totDist += 1 posKnight = [(posKnight[0] + dictMoves[bestMove][0]), (posKnight[1] + dictMoves[bestMove][1])] print(totDist) for x in finalPath: print(x + ' ', end='') def distFormula(i_start, j_start, i_end, j_end): return math.sqrt(pow((i_end - i_start),2) + pow((j_end - j_start),2)) 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)