بتل کد Battle Codeدارد باز می‌شود…

جواب «Degrees of Separation» چالش 6 از جلسه‌ی 35

سؤال

ورودی: یال‌های یک شبکه‌ی دوستی (بدون جهت) <a> <b> تا end، سپس یک خط <from> <to>. با BFS کمترین تعداد گام بین دو نفر را چاپ کنید؛ اگر مسیری نبود یا یکی در شبکه نبود -1. (اگر دو نام یکی بودند، 0.)

راهنما

dist را با {start: 0} شروع کنید؛ هر همسایه‌ی جدید dist[node] + 1 می‌گیرد.

یک جواب درست

from collections import defaultdict, deque

graph = defaultdict(list)
while True:
    line = input()
    if line == "end":
        break
    a, b = line.split()
    graph[a].append(b)
    graph[b].append(a)
src, dst = input().split()
dist = {src: 0}
queue = deque([src])
while queue:
    node = queue.popleft()
    for nxt in graph[node]:
        if nxt not in dist:
            dist[nxt] = dist[node] + 1
            queue.append(nxt)
print(dist.get(dst, -1))

اول خودت امتحان کن؛ جواب‌های دیگر هم قبول است. برگرد و خودت حلش کن