We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
#!/bin/python3importmathimportosimportrandomimportreimportsysfromcollectionsimportdequedefisvalid(x,y,n,visited):if(x,y)invisited:returnFalseifx<0orx>n-1ory<0ory>n-1:returnFalsereturnTruedefprintShortestPath(n,i_start,j_start,i_end,j_end):# Print the distance along with the sequence of moves.moves=[[-2,-1],[-2,1],[0,2],[2,1],[2,-1],[0,-2]]mstr=['UL','UR','R','LR','LL','L']dq=deque()dist=[[n*nforiinrange(n)]forjinrange(n)]visited=set()path=[[[]foriinrange(n)]forjinrange(n)]dq.append((i_start,j_start))dist[i_start][j_start]=0visited.add((i_start,j_start))whilelen(dq)>0:i,j=dq.popleft()forkinrange(len(moves)):nexti=i+moves[k][0]nextj=j+moves[k][1]ifisvalid(nexti,nextj,n,visited):dq.append((nexti,nextj))ifdist[nexti][nextj]>dist[i][j]+1:path[nexti][nextj]=path[i][j]+[mstr[k]]dist[nexti][nextj]=dist[i][j]+1visited.add((nexti,nextj))ifdist[i_end][j_end]>=n*n:print('Impossible')returnprint(dist[i_end][j_end])print(' '.join(path[i_end][j_end]))if__name__=='__main__':n=int(input().strip())first_multiple_input=input().rstrip().split()i_start=int(first_multiple_input[0])j_start=int(first_multiple_input[1])i_end=int(first_multiple_input[2])j_end=int(first_multiple_input[3])printShortestPath(n,i_start,j_start,i_end,j_end)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Red Knight's Shortest Path
You are viewing a single comment's thread. Return to all comments →