Лабиринт задан списком строк: # — стена, . — проход, S — старт, E — выход. За один шаг можно пойти вверх, вниз, влево или вправо. Допишите maze_steps(maze): функция возвращает минимальное число шагов от S до E или -1, если выхода не достичь. Пропуски помечены # TODO.
maze_steps([
"S.#",
".##",
"..E",
]) # 4S и E в лабиринте ровно по одному. Строки одной длины.Заготовка задачи обновилась с тех пор, как вы сохранили свой код.
Сбросить редактор к заготовке? Ваш код будет удалён.
from collections import deque
def maze_steps(maze: list[str]) -> int:
"""Минимальное число шагов от S до E или -1."""
rows, cols = len(maze), len(maze[0])
start = next((r, c) for r in range(rows) for c in range(cols) if maze[r][c] == "S")
dist = {start: 0}
queue = deque([start])
while queue:
r, c = queue.popleft()
if maze[r][c] == "E":
return dist[(r, c)]
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
# TODO: если (nr, nc) внутри поля, не стена и ещё не посещена —
# запишите расстояние и поставьте клетку в очередь
pass
return -1Вывод обрезан: показаны первые строки.
def test_example():
"""Пример из условия → 4"""
got = maze_steps(["S.#", ".##", "..E"])
assert got == 4, f"ожидалось 4, получено {got!r}"
def test_adjacent():
"""Выход рядом → 1"""
got = maze_steps(["SE"])
assert got == 1, f"ожидалось 1, получено {got!r}"
def test_blocked():
"""Выход замурован → -1"""
got = maze_steps(["S.#", "###", "#.E"])
assert got == -1, f"ожидалось -1, получено {got!r}"
def test_one_column():
"""Узкий коридор в одну клетку шириной"""
got = maze_steps(["S", ".", ".", "E"])
assert got == 3, f"ожидалось 3, получено {got!r}"
def test_shortest_of_two():
"""Из двух путей выбирается короткий"""
maze = [
"S....",
".###.",
".#E..",
".###.",
".....",
]
got = maze_steps(maze)
assert got == 8, f"ожидалось 8 (верхний путь; нижний — 12), получено {got!r}"
def test_no_wrap_around():
"""С края поля нельзя «перепрыгнуть» на другой край"""
got = maze_steps(["E#S"])
assert got == -1, f"ожидалось -1, получено {got!r}"
def test_big_open_field():
"""Открытое поле 60×60 из угла в угол"""
maze = ["." * 60 for _ in range(60)]
maze[0] = "S" + maze[0][1:]
maze[-1] = maze[-1][:-1] + "E"
got = maze_steps(maze)
assert got == 118, f"ожидалось 118, получено {got!r}"Можно решать и в своём редакторе: «Скопировать с тестами» и запустите python3 maze_steps.py — тесты те же, результат покажет ✓ / ✗ и итог.
Граф здесь не задан словарём: соседи клетки (r, c) — это четыре клетки вокруг неё, если они внутри поля и не стены.
Проверка соседа: 0 <= nr < rows, 0 <= nc < cols, maze[nr][nc] != '#', клетки ещё нет в dist.
from collections import deque
def maze_steps(maze: list[str]) -> int:
"""Минимальное число шагов от S до E или -1."""
rows, cols = len(maze), len(maze[0])
start = next((r, c) for r in range(rows) for c in range(cols) if maze[r][c] == "S")
dist = {start: 0}
queue = deque([start])
while queue:
r, c = queue.popleft()
if maze[r][c] == "E":
return dist[(r, c)]
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 maze[nr][nc] != "#" and (nr, nc) not in dist:
dist[(nr, nc)] = dist[(r, c)] + 1
queue.append((nr, nc))
return -1