Snakes and Ladders: The Quickest Way Up

  • + 0 comments

    BFS algorithm.

        # BFS
        path={}
        for x in ladders+snakes:
            path[x[0]]=x[1]
    
        qu=[(1,0)]
        visit=set({1})
        while len(qu)>0:
            cur,step=qu.pop(0)
            if cur>=100:
                return step
            for i in range(1,7):
                if cur+i in path:
                    nxt=path[cur+i]
                else:
                    nxt=cur+i
                if nxt not in visit:
                    visit.add(nxt)
                    qu.append((nxt,step+1))
        
        return -1