#!/bin/python #Ah, I think 10 is an edge case and it's causing my while loop to go on forever. Let me cover the edge cases. #I'm gonna first attempt to do so just using a time-related impossible return because I'm lazy and awful lol. import sys import time def sortByPriority(moveOut): #priority UL, UR, R, LR, LL, L #print("moveOut",moveOut) moveOut = moveOut.split(" ") L = moveOut.count("L") R = moveOut.count("R") LL = moveOut.count("LL") LR = moveOut.count("LR") UL = moveOut.count("UL") UR = moveOut.count("UR") daStuff = [UL, UR, R, LR, LL, L] daLetters = ["UL", "UR", "R", "LR", "LL", "L"] sortacular = "" for i in range(len(daStuff)): for _ in range(daStuff[i]): sortacular += (daLetters[i]+" ") sortacular = sortacular[:-1] return sortacular def printShortestPath(n, i_start, j_start, i_end, j_end): startTime = time.time() #i = y-axis #j = x-axis startx = j_start starty = i_start endx = j_end endy = i_end #L = startx -= 2 #R = startx += 2 #LL = starty += 2 and startx -= 1 #LR = starty += 2 and startx += 1 #UL = starty -= 2 and startx -= 1 #UR = starty -= 2 and startx += 1 #Alright so we can always move along x in increments of one, so something can never be impossible from x-distance except for rare #small cases where LL,LR,UL,and UR are all impossible to navigate around with sufficiently or at all. #I'm not gonna handle edge cases right now, I'm just gonna try and figure out the general idea. #print("startx",startx) #print("starty",starty) #print("endx",endx) #print("endy",endy) #So yeah we can never fix an issue where we are y-misaligned # formally, starty is even or odd, and if endy is the opposite of whatever starty is, it's impossible. if ((starty % 2) == 0 and (endy % 2) == 1) or ((starty % 2) == 1 and (endy % 2) == 0): return "Impossible","Impossible" else: moveOut = "" def move(moveStr,moveOut,startx,starty): if moveStr == "L": startx -= 2 elif moveStr == "R": startx += 2 elif moveStr == "LL": starty += 2 startx -= 1 elif moveStr == "LR": starty += 2 startx += 1 elif moveStr == "UL": starty -= 2 startx -= 1 elif moveStr == "UR": starty -= 2 startx += 1 moveOut += (moveStr+" ") return moveOut,startx,starty moveCount = 0 bothEqual = False #priority UL, UR, R, LR, LL, L while bothEqual == False: currentTime = time.time() if (currentTime - startTime) > 2: return "Impossible","Impossible" if startx > endx and starty > endy: distx = startx-endx disty = starty-endy #print("firstExample disty/2",(disty/2)) if distx > (disty/2): moveOut,startx,starty = move("L",moveOut,startx,starty) moveCount += 1 #print(moveOut,startx,starty) elif distx == (disty/2): moveOut,startx,starty = move("UL",moveOut,startx,starty) moveCount += 1 #print(moveOut,startx,starty) elif distx < (disty/2): moveOut,startx,starty = move("UR",moveOut,startx,starty) moveCount += 1 #print(moveOut,startx,starty) elif startx < endx and starty > endy: distx = endx-startx disty = starty-endy #print("firstExample disty/2",(disty/2)) if distx > (disty/2): moveOut,startx,starty = move("R",moveOut,startx,starty) moveCount += 1 #print(moveOut,startx,starty) elif distx == (disty/2): moveOut,startx,starty = move("UR",moveOut,startx,starty) moveCount += 1 #print(moveOut,startx,starty) elif distx < (disty/2): moveOut,startx,starty = move("UL",moveOut,startx,starty) moveCount += 1 #print(moveOut,startx,starty) elif startx > endx and starty < endy: distx = startx-endx disty = endy-starty #print("firstExample disty/2",(disty/2)) if distx > (disty/2): moveOut,startx,starty = move("L",moveOut,startx,starty) moveCount += 1 #print(moveOut,startx,starty) elif distx == (disty/2): moveOut,startx,starty = move("LL",moveOut,startx,starty) moveCount += 1 #print(moveOut,startx,starty) elif distx < (disty/2): moveOut,startx,starty = move("LR",moveOut,startx,starty) moveCount += 1 #print(moveOut,startx,starty) elif startx < endx and starty < endy: distx = endx-startx disty = endy-starty #print("firstExample disty/2",(disty/2)) if distx > (disty/2): moveOut,startx,starty = move("R",moveOut,startx,starty) moveCount += 1 #print(moveOut,startx,starty) elif distx == (disty/2): moveOut,startx,starty = move("LR",moveOut,startx,starty) moveCount += 1 #print(moveOut,startx,starty) elif distx < (disty/2): moveOut,startx,starty = move("LL",moveOut,startx,starty) moveCount += 1 #print(moveOut,startx,starty) elif startx > endx and starty == endy: moveOut,startx,starty = move("L",moveOut,startx,starty) moveCount += 1 #print(moveOut,startx,starty) elif startx < endx and starty == endy: moveOut,startx,starty = move("R",moveOut,startx,starty) moveCount += 1 #print(moveOut,startx,starty) elif startx == endx and starty > endy: moveOut,startx,starty = move("UL",moveOut,startx,starty) moveCount += 1 #print(moveOut,startx,starty) elif startx == endx and starty < endy: moveOut,startx,starty = move("LR",moveOut,startx,starty) moveCount += 1 #print(moveOut,startx,starty) if startx == endx and starty == endy: bothEqual = True moveOut = moveOut[:-1] moveOut = sortByPriority(moveOut) #print(startx,starty,endx,endy,moveOut) return moveCount,moveOut #moveOut,startx,starty = move("L",moveOut,startx,starty) #print(moveOut,startx,starty,endx,endy) if __name__ == "__main__": n = int(raw_input().strip()) i_start, j_start, i_end, j_end = raw_input().strip().split(' ') i_start, j_start, i_end, j_end = [int(i_start), int(j_start), int(i_end), int(j_end)] mc,mo = printShortestPath(n, i_start, j_start, i_end, j_end) if mc == "Impossible": print(mc) else: print(mc) print(mo)