Medium BFS on Board Graphs
In plain English: Find the minimum number of dice rolls to reach square 100 on a snakes-and-ladders board.
Model the board as a graph where each square connects to the 6 dice outcomes — BFS then finds the minimum rolls to reach 100.
Prompt
Find minimum dice rolls to reach square 100 on a snakes-and-ladders board.
Try to write it from scratch before scrolling down.
Solution
from collections import deque
def snakes_ladders(board):
# board: dict {position: destination}
target = 100
dist = {1: 0}
q = deque([1])
while q:
pos = q.popleft()
if pos == target:
return dist[pos]
for dice in range(1, 7): # each dice roll = one edge
nxt = pos + dice
if nxt > target:
continue
if nxt in board:
nxt = board[nxt]
if nxt not in dist:
dist[nxt] = dist[pos] + 1
q.append(nxt)
return -1