[ prog / sol / mona ]

sol


Code

1 2022-05-09 04:44

from collections import deque

def minimum_turns(snakes, ladders): # Create a board with the given snakes and ladders.

board = {square: square for square in range(1, 101)}

for start, end in snakes.items():

board[start] = end

for start, end in ladders.items():

board[start] = end

# Perform BFS to reach the last square as quickly as possible.

start, end = 0, 100

turns = 0

path = deque([(start, turns)])

visited = set()

while path:

square, turns = path.popleft()

for move in range(square + 1, square + 7):

if move >= end:

return turns + 1

if move not in visited:

visited.add(move)

path.append((board[move], turns + 1))

9


VIP:

do not edit these