#!/bin/python3 import sys global i,j ,size,moves,path i=0 j=0 size=0 path=[] moves=0 def onColumn(i_end,j_end): global i,j if(j==j_end): return True else: return False def onRow(i_end,j_end): global i,j if(i==i_end): return True else: return False def isLeft(i_end,j_end): global i,j if(jj_end): return True else: return False def isBelow(i_end,j_end): global i,j if(i>i_end): return True else: return False def isAbove(i_end,j_end): global i,j if(i=0 and i=0 and jj_start): return 1 elif(i_endi_start and j_end>j_start): return 3 elif(i_end>i_start and j_endj_start): return 5 elif(i_end==i_start and j_endi_start and j_end==j_start): return 8 def print_path(): for temp in path: print(temp, end=" ") def UR_main(i_start, j_start, i_end, j_end): global i,j,moves,path while(UR()!=False): path.append("UR") moves=moves+1 if(check_target(i,j,i_end,j_end)==0): print(moves) print_path() return elif(onRow(i_end,j_end)==True): while(isRight(i_end,j_end)==False and R()!=False): path.append("R") moves=moves+1 if(check_target(i,j,i_end,j_end)==0): print(moves) print_path() return elif(onColumn(i_end,j_end)==True): ch=check_target(i,j,i_end,j_end) if(ch==7): CT_main(i,j,i_end,j_end) return elif(ch==8): CD_main(i,j,i_end,j_end) return print("Impossible") def UL_main(i_start, j_start, i_end, j_end): global i,j,moves,path while(UL()!=False): path.append("UL") moves=moves+1 if(check_target(i,j,i_end,j_end)==0): print(moves) print_path() return elif(onRow(i_end,j_end)==True): while(isLeft(i_end,j_end)==False and L()!=False): path.append("L") moves=moves+1 if(check_target(i,j,i_end,j_end)==0): print(moves) print_path() return elif(onColumn(i_end,j_end)==True): ch=check_target(i,j,i_end,j_end) if(ch==7): CT_main(i,j,i_end,j_end) return elif(ch==8): CD_main(i,j,i_end,j_end) return print("Impossible") def LR_main(i_start, j_start, i_end, j_end): global i,j,moves,path while(LR()!=False): path.append("LR") moves=moves+1 if(check_target(i,j,i_end,j_end)==0): print(moves) print_path() return elif(onRow(i_end,j_end)==True): while(isRight(i_end,j_end)==False and R()!=False): path.append("R") moves=moves+1 if(check_target(i,j,i_end,j_end)==0): print(moves) print_path() return elif(onColumn(i_end,j_end)==True): ch=check_target(i,j,i_end,j_end) if(ch==7): CT_main(i,j,i_end,j_end) return elif(ch==8): CD_main(i,j,i_end,j_end) return print("Impossible") def LL_main(i_start, j_start, i_end, j_end): global i,j,moves,path while(LL()!=False): path.append("UL") moves=moves+1 if(check_target(i,j,i_end,j_end)==0): print(moves) print_path() return elif(onRow(i_end,j_end)==True): while(isLeft(i_end,j_end)==False and L()!=False): path.append("L") moves=moves+1 if(check_target(i,j,i_end,j_end)==0): print(moves) print_path() return elif(onColumn(i_end,j_end)==True): ch=check_target(i,j,i_end,j_end) if(ch==7): CT_main(i,j,i_end,j_end) return elif(ch==8): CD_main(i,j,i_end,j_end) return print("Impossible") def RR_main(i_start, j_start, i_end, j_end): global i,j,moves,path while(isRight(i_end,j_end)==False and R()!=False): moves=moves+1 path.append("R") if(check_target(i,j,i_end,j_end)==0): print(moves) print_path() return print("Impossible") def RL_main(i_start, j_start, i_end, j_end): global i,j,moves,path while(isRight(i_end,j_end)==False and L()!=False): moves=moves+1 path.append("L") if(check_target(i,j,i_end,j_end)==0): print(moves) print_path() return print("Impossible") def CT_main(i_start, j_start, i_end, j_end): global i,j,moves,path if(abs(i_end-i_start)%4==0): #code for calculation moves and paths moves=moves+int(2*abs(i_end-i_start)/4) if(UL()!=False): for k in range(0,int(moves/2)): path.append("UL") path.append("UR") print(moves) print_path() elif(UR()!=False): for k in range(0,int(moves/2)): path.append("UR") path.append("UL") print(moves) print_path() else: print("Impossible") def CD_main(i_start, j_start, i_end, j_end): global i,j,moves,path if(abs(i_end-i_start)%4==0): #code for calculation moves and paths moves=moves+int(2*abs(i_end-i_start)/4) if(LR()!=False): for k in range(0,int(moves/2)): path.append("LR") path.append("LL") print(moves) print_path() elif(LL()!=False): for k in range(0,int(moves/2)): path.append("LL") path.append("LR") print(moves) print_path() else: print("Impossible") def printShortestPath(n, i_start, j_start, i_end, j_end): ch=check_target(i_start,j_start,i_end,j_end) global i,j,size,moves if(ch==0): print(moves) elif(ch==1): UR_main(i_start,j_start,i_end,j_end) elif(ch==2): UL_main(i_start,j_start,i_end,j_end) elif(ch==3): LR_main(i_start,j_start,i_end,j_end) elif(ch==4): LL_main(i_start,j_start,i_end,j_end) elif(ch==5): RR_main(i_start,j_start,i_end,j_end) elif(ch==6): RL_main(i_start,j_start,i_end,j_end) elif(ch==7): CT_main(i_start,j_start,i_end,j_end) elif(ch==8): CD_main(i_start,j_start,i_end,j_end) if __name__ == "__main__": n = int(input().strip()) size=n 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)] i=i_start j=j_start printShortestPath(n, i_start, j_start, i_end, j_end)