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

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

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