#!/bin/python import sys def validSpot(n, i_start, j_start, i_end, j_end): if abs(i_start-i_end)%4==0 and abs(j_start-j_end)%2==0: return True elif abs(i_start-i_end)%4==2 and abs(j_start-j_end)%2==1: return True else: print "Impossible" return False def printShortestPath(n, i_start, j_start, i_end, j_end,ans): # Print the distance along with the sequence of moves. if i_start==i_end and j_start==j_end: print len(ans.split()) y = ans.split() l = [] for z in range(0,len(y)): if y[z]=='UL': l.append(0) if y[z]=='UR': l.append(1) if y[z]=='R': l.append(2) if y[z]=='LR': l.append(3) if y[z]=='LL': l.append(4) if y[z]=='L': l.append(5) l.sort() ans="" for z in range(0,len(l)): if l[z]==0: ans+="UL " if l[z]==1: ans+="UR " if l[z]==2: ans+="R " if l[z]==3: ans+="LR " if l[z]==4: ans+="LL " if l[z]==5: ans+="L " print ans return 0 if j_end>j_start and i_end==i_start: ans=ans+"R " return printShortestPath(n,i_start,j_start+2,i_end,j_end,ans) elif j_endj_start and i_end=j_start and i_end>i_start: ans=ans+"LR " return printShortestPath(n,i_start+2,j_start+1,i_end,j_end,ans) elif j_endi_start: ans=ans+"LL " return printShortestPath(n,i_start+2,j_start-1,i_end,j_end,ans) elif j_end<=j_start and i_end