Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import sys
- def main():
- l = [1,0,0,0,0,0,0,1,1]
- #initialize a result list, each entry keeps the best number of steps to reach here and the previous hop
- size = len(l)
- result=[(-1,-1)]*size
- #if we only have one element, print 0,out
- if(size==1):
- print ("0,out")
- return
- #In case that we only do one fly. We need to preload the result list
- result[0]=(0,0)
- maxStepZero =l[0]
- if (maxStepZero >= size-1):
- print ("0,"+str(size-1)+",out")
- return
- else:
- for i in range (1,1+maxStepZero):
- result[i] = (1,0)
- for i in range (1,size-1):
- numHopI,prevI = result[i];
- print ("Stuck")
- for j in range (i+1,min(size,i+1+l[i])):
- if(numHopI == -1):
- print("failurejjj")
- return
- numHopJ,prevJ = result[j]
- # Update the result list if we could explore a new field with one additonal fly
- if (numHopJ == -1):
- result[j] = (numHopI+1,i)
- # If the destination can never explored, we return failure
- numStep,prevN = result[size-1]
- if (numStep == -1):
- print ("failure")
- return
- # Trace the route ,and reverse to get the order from beginning to the end
- resultSeq =[] #The reverse sequence of the result
- resultSeq.append(size-1)
- resultSeq.append(prevN)
- while True:
- numStep,prevN = result[prevN]
- resultSeq.append(prevN)
- if prevN == 0:
- break;
- resultSeq.reverse()
- for stop in resultSeq :
- print (str(stop)+",")
- print ("out")
- return
- if __name__=="__main__":
- main()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement