Giả sử chúng ta đang chơi trò chơi rắn và thang. Chúng tôi có một điều kiện là có thể tung bất kỳ số nào mà chúng tôi có thể thích trên một viên xúc xắc. Chúng tôi bắt đầu từ vị trí 0 và điểm đến của chúng tôi là vị trí 100, và chúng tôi tung xúc xắc nhiều lần để đến đích. Chúng ta phải tìm ra số lượng cuộn xúc xắc ít nhất cần thiết để đến đích nếu chúng ta được cung cấp vị trí của các con rắn và thang trên bàn cờ. các mảng chứa giá trị bắt đầu và giá trị kết thúc của một con rắn hoặc một bậc thang trên bảng.
Vì vậy, nếu đầu vào giống như thang =[(11, 40), (37,67), (47, 73), (15, 72)], rắn =[(90, 12), (98, 31), (85, 23), (75, 42), (70, 18), (49, 47)], thì đầu ra sẽ là 8.
Số lần di chuyển tối thiểu cần có là 8 để đạt được vị trí thứ 100 trên bàn cờ với các vị trí của rắn và thang.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- nối mảng rắn vào thang mảng
- edge:=một bản đồ mới
- đối với mỗi cặp f, t trong thang, thực hiện
- các cạnh [f]:=t
- u:=một tập hợp mới
- v:=một tập hợp mới
- thêm (1) vào v
- m:=0
- trong khi 100 không có trong v, hãy thực hiện
- m:=m + 1
- w:=một tập hợp mới
- đối với mỗi f trong v, thực hiện
- đối với tôi trong phạm vi từ 1 đến 6, hãy thực hiện
- n:=f + i
- nếu n có trong các cạnh, thì
- n:=edge [n]
- nếu n có trong u, thì
- chuyển sang lần lặp tiếp theo
- thêm (n) vào u
- thêm (n) vào w
- đối với tôi trong phạm vi từ 1 đến 6, hãy thực hiện
- v:=w
- trả lại m
Ví dụ
Hãy cùng chúng tôi xem cách 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