Giả sử ta chơi trò Rắn Cầu Thang. Điều kiện: ta có thể gieo xúc xắc ra bất kỳ số nào (1-6). Bắt đầu từ vị trí 0, đích là 100. Cho trước vị trí rắn và thang (mảng snakes và ladders, mỗi phần tử là cặp (start, end)). Tìm số lần gieo xúc xắc tối thiểu để đến đích.
Ví dụ: ladders = [(11, 40), (37,67), (47, 73), (15, 72)], snakes = [(90, 12), (98, 31), (85, 23), (75, 42), (70, 18), (49, 47)], đầu ra = 8.
Giải pháp
Đây là bài toán tìm đường đi ngắn nhất trên đồ thị không trọng số, dùng BFS:
- Gộp mảng snakes vào ladders
- edges := map mới
- Với mỗi cặp f,t trong ladders: edges[f] := t
- u := tập hợp mới, v := tập hợp mới, thêm 1 vào v
- m := 0
- Khi 100 không trong v:
- m := m + 1
- w := tập hợp mới
- Với mỗi f trong v:
- Với i từ 1 đến 6:
- n := f + i
- Nếu n trong edges: n := edges[n]
- Nếu n trong u: tiếp tục
- Thêm n vào u và w
- Với i từ 1 đến 6:
- v := w
- Trả về m
Ví dụ minh họa
Xem triển khai sau để hiểu rõ hơn:
def solve(ladders, snakes):
ladders.extend(snakes)
edges = {}
for f, t in ladders:
edges[f] = t
u = set()
v = set()
v.add(1)
m = 0
while 100 not in v:
m += 1
w = set()
for f in v:
for i in range(1, 7):
n = f + i
if n in edges:
n = edges[n]
if n in u:
continue
u.add(n)
w.add(n)
v = w
return m
print(solve([(11, 40), (37,67), (47, 73), (15, 72)], [(90, 12), (98, 31), (85, 23), (75, 42), (70, 18), (49, 47)]))
Đầu vào
[(11, 40), (37,67), (47, 73), (15, 72)], [(90, 12), (98, 31), (85, 23), (75, 42), (70, 18), (49, 47)]
Đầu ra
8