Snakes and Ladders: The Quickest Way Up

  • + 0 comments
    def quickestWayUp(ladders, snakes):
        # Write your code here
        temp = {}
        for a, b in ladders + snakes:
            temp[a] = b
            
        graph = {}
        for i in range(1, 100):
            if i not in temp :
                graph[i] = []
                for roll in range(1, 7):
                    pos = i+roll
                    if pos <= 100:
                        pos = temp.get(pos, pos)
                        graph[i].append(pos)
        visited = set()          
        queue = deque()
        queue.append((1, 0))
        visited.add(1)
        while len(queue) > 0:
            current, roll_count = queue.popleft()
            if current == 100:
                return roll_count
            
            for n in graph[current]:
                if n not in visited:
                    queue.append((n, roll_count+1))
                    visited.add(n)
                    
        return -1