جواب «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))
اول خودت امتحان کن؛ جوابهای دیگر هم قبول است. برگرد و خودت حلش کن