Snakes and Ladders: The Quickest Way Up

  • + 0 comments

    Python3 solution:

    def quickestWayUp(ladders, snakes):
        # Write your code here
        graph1 = dict()
        for u, v in ladders:
            graph1[u] = v
        graph2 = dict()
        for u, v in snakes:
            graph2[u] = v
        q = deque()
        visit = set()
        q.append([1, 0])
        while(q): 
            square, moves = q.popleft()
            for i in range(1, 7):
                next_square = square + i
                if graph1.get(next_square):
                    next_square = graph1.get(next_square)
                elif graph2.get(next_square):
                    next_square = graph2.get(next_square)
                
                if next_square == 100:
                    return moves + 1
                if next_square not in visit:
                    visit.add(next_square)
                    q.append([next_square, moves+1])
                
        return -1