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

جواب «Step 2: Reachability» چالش 2 از جلسه‌ی 36

سؤال

گام ۲. با BFS از S (حرکت چهارجهته، فقط خانه‌های غیر دیوار، بدون خروج از نقشه) همه‌ی خانه‌های قابل‌دسترسی را پیدا کنید. اگر ماز نامعتبر بود invalid maze، وگرنه دو خط: reachable: <تعداد خانه‌های قابل‌دسترسی شامل S> و exit: yes یا exit: no.

راهنما

یک set از خانه‌های دیده‌شده و یک deque کافی است؛ پیش از دسترسی به grid[nr][nc] بازه را بررسی کنید.

یک جواب درست

from collections import deque


def read_maze():
    grid = []
    while True:
        line = input()
        if line == "end":
            break
        grid.append(line)
    return grid


def find(grid, ch):
    for r, row in enumerate(grid):
        c = row.find(ch)
        if c != -1:
            return (r, c)
    return None


def reachable(grid, start):
    rows, cols = len(grid), len(grid[0])
    seen = {start}
    queue = deque([start])
    while queue:
        r, c = queue.popleft()
        for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#" and (nr, nc) not in seen:
                seen.add((nr, nc))
                queue.append((nr, nc))
    return seen


grid = read_maze()
start, goal = find(grid, "S"), find(grid, "E")
if start is None or goal is None:
    print("invalid maze")
else:
    seen = reachable(grid, start)
    print(f"reachable: {len(seen)}")
    print("exit: yes" if goal in seen else "exit: no")

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