جواب «Step 4: Draw the Path» چالش 4 از جلسهی 36
سؤال
گام ۴. مسیر کوتاهترین را بازسازی و روی نقشه رسم کنید. ترتیب بررسی همسایهها: بالا، پایین، چپ، راست؛ والد هر خانه اولین خانهای است که آن را کشف کرده. خانههای مسیر (بهجز S و E) را با * علامت بزنید، نقشه را خطبهخط چاپ کنید و سپس steps: <n>. اگر راهی نبود فقط no path و اگر ماز نامعتبر بود invalid maze.
راهنما
رشتهها تغییرناپذیرند؛ ماز را به لیستی از لیستها (list(row)) تبدیل کنید، علامت بزنید و با "".join چاپ کنید.
یک جواب درست
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
MOVES = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def bfs(grid, start):
rows, cols = len(grid), len(grid[0])
parent = {start: None}
dist = {start: 0}
queue = deque([start])
while queue:
r, c = queue.popleft()
for dr, dc in MOVES:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#" and (nr, nc) not in dist:
dist[(nr, nc)] = dist[(r, c)] + 1
parent[(nr, nc)] = (r, c)
queue.append((nr, nc))
return dist, parent
grid = read_maze()
start, goal = find(grid, "S"), find(grid, "E")
if start is None or goal is None:
print("invalid maze")
else:
dist, parent = bfs(grid, start)
if goal not in dist:
print("no path")
else:
cells = [list(row) for row in grid]
node = parent[goal]
while node != start:
r, c = node
cells[r][c] = "*"
node = parent[node]
for row in cells:
print("".join(row))
print(f"steps: {dist[goal]}")
اول خودت امتحان کن؛ جوابهای دیگر هم قبول است. برگرد و خودت حلش کن