جواب «Is There a Way Out?» چالش 5 از جلسهی 41
سؤال
has_path(rows) با BFS بررسی کند از S به G راه هست یا نه: اول جای S را پیدا کن؛ صف queue و مجموعهی seen با همان خانه. تا صف خالی نشده، اولی را بردار؛ اگر G بود True؛ وگرنه چهار همسایه را که # نیستند و دیده نشدهاند اضافه کن. آخر False. (دیوار دور تا دور هست، پس از مرحله بیرون نمیزنی.) خروجی test: True، False، True.
راهنما
مثل جلسهی ۱۴: r, c = queue.pop(0) و for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:.
یک جواب درست
def has_path(rows):
start = None
for r in range(len(rows)):
for c in range(len(rows[r])):
if rows[r][c] == "S":
start = (r, c)
seen = {start}
queue = [start]
while queue:
r, c = queue.pop(0)
if rows[r][c] == "G":
return True
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nxt = (r + dr, c + dc)
if rows[nxt[0]][nxt[1]] != "#" and nxt not in seen:
seen.add(nxt)
queue.append(nxt)
return False
# ---- test (do not change) ----
print(has_path(["#####", "#S..#", "#.#.#", "#..G#", "#####"]))
print(has_path(["#####", "#S#.#", "###.#", "#..G#", "#####"]))
print(has_path(["#######", "#S....#", "#####.#", "#G....#", "#######"]))
اول خودت امتحان کن؛ جوابهای دیگر هم قبول است. برگرد و خودت حلش کن