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

جواب «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....#", "#######"]))

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