Advertisement
Guest User

Untitled

a guest
Oct 22nd, 2014
171
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.72 KB | None | 0 0
  1. import sys
  2.  
  3. def main():
  4. l = [1,0,0,0,0,0,0,1,1]
  5.  
  6. #initialize a result list, each entry keeps the best number of steps to reach here and the previous hop
  7. size = len(l)
  8. result=[(-1,-1)]*size
  9.  
  10. #if we only have one element, print 0,out
  11. if(size==1):
  12. print ("0,out")
  13. return
  14. #In case that we only do one fly. We need to preload the result list
  15. result[0]=(0,0)
  16. maxStepZero =l[0]
  17. if (maxStepZero >= size-1):
  18. print ("0,"+str(size-1)+",out")
  19. return
  20. else:
  21. for i in range (1,1+maxStepZero):
  22. result[i] = (1,0)
  23.  
  24. for i in range (1,size-1):
  25. numHopI,prevI = result[i];
  26.  
  27. print ("Stuck")
  28. for j in range (i+1,min(size,i+1+l[i])):
  29. if(numHopI == -1):
  30. print("failurejjj")
  31. return
  32. numHopJ,prevJ = result[j]
  33. # Update the result list if we could explore a new field with one additonal fly
  34. if (numHopJ == -1):
  35. result[j] = (numHopI+1,i)
  36.  
  37. # If the destination can never explored, we return failure
  38. numStep,prevN = result[size-1]
  39. if (numStep == -1):
  40. print ("failure")
  41. return
  42.  
  43. # Trace the route ,and reverse to get the order from beginning to the end
  44. resultSeq =[] #The reverse sequence of the result
  45. resultSeq.append(size-1)
  46. resultSeq.append(prevN)
  47. while True:
  48. numStep,prevN = result[prevN]
  49. resultSeq.append(prevN)
  50. if prevN == 0:
  51. break;
  52.  
  53. resultSeq.reverse()
  54. for stop in resultSeq :
  55. print (str(stop)+",")
  56. print ("out")
  57. return
  58.  
  59. if __name__=="__main__":
  60. main()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement