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