Нахождение кратчайшего пути в лабиринте (массиве) с визуализацией в Python
Получила в университете следующее задание.
Создайте лабиринт в Python Используйте соответствующую структуру данных для внутреннего представления лабиринта, предпочтительно массив NumPy.
Визуализируйте лабиринт Самый простой способ визуализировать лабиринт - преобразовать его в символьное / строковое представление (ASCII-art) и просто записать его в консоль или вывод записной книжки с помощью функции print (), как показано выше. Если у вас уже есть продвинутый опыт работы с Python, вы также можете полагаться на графические представления.
Определить путь Путь может быть получен эвристическим или точным способом. Вам разрешено использовать для этой цели соответствующую библиотеку, но вы также можете реализовать алгоритм самостоятельно .
Распечатайте путь а. Текстовая форма (координаты): (x1, y1) -> (x2, y2) -> б. Графическая (ASCII или растровая) форма, в зависимости от того, что вы выбрали на шаге 2).
В интернете нашла код и преобразовала его под свои данные:
M = 20 # Rows
N = 50 # Columns
def isSafe(grid,visited,x,y):
if grid[x][y]=='#' or visited[x][y]==True:
return False # Unsafe
return True # Safe
def isValid(x,y):
if x<M and y<N and x>=0 and y>=0:
return True # Valid
return False # Invalid
def solve(grid,visited,i,j,dest_x,dest_y,curr_dist,min_dist,shortestPath,currentPath):
if i==dest_x and j==dest_y: # if destination is found, update min_dist
if curr_dist<min_dist[0]: # If a shorter distance is found
min_dist[0] = curr_dist # Update distance
shortestPath.clear() # Update path
shortestPath.extend(currentPath)
shortestPath.append((dest_y,dest_x)) # Push the destination coordinates
return
# set (i, j) cell as visited
visited[i][j] = True
currentPath.append((j,i))
# go to bottom cell
if isValid(i + 1, j) and isSafe(grid,visited,i + 1, j):
solve(grid,visited,i + 1, j, dest_x, dest_y, curr_dist + 1,min_dist,shortestPath,currentPath)
# go to right cell
if isValid(i, j + 1) and isSafe(grid,visited,i, j + 1):
solve(grid,visited,i, j + 1, dest_x, dest_y, curr_dist + 1,min_dist,shortestPath,currentPath)
# go to top cell
if isValid(i - 1, j) and isSafe(grid,visited,i - 1, j):
solve(grid,visited,i - 1, j, dest_x, dest_y, curr_dist + 1,min_dist,shortestPath,currentPath)
# go to left cell
if isValid(i, j - 1) and isSafe(grid,visited,i, j - 1):
solve(grid,visited,i, j - 1, dest_x, dest_y, curr_dist + 1,min_dist,shortestPath,currentPath)
visited[i][j] = False
currentPath.pop()
if __name__ == "__main__":
min_dist = [9e10] # Start from infinity
shortestPath = [] # It will contain the path (y,x) tuples
currentPath = [] # It will store the current path temporarily
grid = [
['-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','T','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|','S',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-']
]
visited = []
for i in range(M):
_list = list()
for j in range(N):
_list.append(False)
visited.append(_list)
solve(grid,visited,M-1,0,0,N-1,0,min_dist,shortestPath,currentPath)
print("Minimum distance: ",min_dist[0])
print("Path: [",end=" ")
for path in shortestPath:
print('('+str(path[0])+','+str(path[1])+')',end=' ')
print("]")
Получаю ошибку:
list indices must be integers or slices, not tuple
Пробовала и такую программу:
from collections import deque
maze = [
['-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','T','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['|','S',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','|']
['-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-']
]
def print_field(field, path = None):
field = maze.readlines()
n = len(field)
m = len(field[0]) - 1
s = None
t = None
for i in range(n):
field[i] = field[i].strip()
if field[i].find('S') !=-1:
s = (i, field[i].find('S'))
if field[i].find('T') != -1:
t = (i, field[i].find('T'))
print_field(field)
print(s,t)
def bfs(field, S, T):
n = len(field)
m = len(field[0])
INF = 10**9
delta = [(0,-1), (0,1), (1,0), (-1,0)]
d = [[INF]]*m for _ in range(n)]
p = [[None]]*m for _ in range(n)]
used = [[False]*m for _ in range(n)]
queue = dequeue()
d[s[0]][s[1]] = 0
used[s[0]][s[1]] = True
queue.append(s)
while len(queue) != 0:
x, y = queue.popleft()
for dx, dy in delta:
nx, ny = x+dx, y+dy
if 0 < nx < n and 0 < ny < m and not used[nx][ny] and field[nx][ny] != '#':
d[nx][ny] = d[x][y] + 1
p[nx][ny] = (x, y))
used[nx][ny] = True
queue.append((nx, ny))
print(d[t[0]][t[1]])
cur = t
path = []
while cure is not None:
path.append(cur)
cur = p[cur[0]][cur[1]]
path.reverse()
print_field(field, path[1:-1])
Получаю ошибку:
File "<ipython-input-7-c2320f90efab>", line 49
d = [[INF]]*m for _ in range(n)]
^
SyntaxError: invalid syntax
Уже голову сломала, ничего не получается! В университете с подобными задачами не работали, программирую в Питоне недавно, поэтому самой разобраться сложно. Буду очень благодарна за помощь!
Если знаете другие способы нахождения кратчайшего пути с использованием NumPy, то поделитесь информацией, пожалуйста! (такой вид у лабиринта 
был определен преподавателем)
Ответы (1 шт):
Автор решения: Vitalizzare ушел в монастырь
→ Ссылка
Об ошибках в используемом коде
Ошибка TypeError: list indices must be integers or slices, not tuple возникает из-за отсутствия запятых между элементами списков grid и maze. Когда Python видит открывающую квадратную скобку сразу после закрывающей, то интерпретирует это как извлечение элемента списка по индексу. Если во второй паре скобок идет перечисление чего-то через запятую, то это воспринимается как tuple, но он не применим к списку в качестве индекса. Пример:
[1, 2, 3][4, 5, 6] # из списка [1, 2, 3] взять элемент по индексу (4, 5, 6)
^^^^^^^^^
Ошибка: использование кортежа (4, 5, 6) в качестве индекса списка [1, 2, 3]
Чтобы минимизировать такие ошибки, мы можем преобразовать текст, представляющий поле лабиринта, в двумерную матрицу символов таким образом::
grid = """
--------------------------------------------------
| # T|
| # |
| # |
| # |
| # |
| # # |
| # # |
| # # |
| # # |
| # # |
| # # |
| # # |
| # # |
| # # |
| # # |
| # |
| # |
| # |
| # |
|S # |
--------------------------------------------------
"""
grid = [*map(list, grid.strip().splitlines())]
Также замечу, что стена указана в isSafe как '#', но на карте обозначена тремя символами -|#. Исправляем либо указав стену на поле одним символом, либо заменив в isSafe проверку равенства на проверку вхождения в набор символов стены.
Кроме этого, у вас количество строк и столбцов не привязано к размеру реального поля, а жестко записано числом. В какой-то момент заданное количество строк M перестало совпадают с размером grid. Исправляем либо строя поле отталкиваясь от заданных размеров, либо вычисляем размеры реально заданного поля.
Об алгоритмах поиска решения
Об алгоритмах можно сказать следующее. В первом вы перебираете все (включая тупиковые, зигзагообразные, дублирующие друг друга) не пересекающие себя линии, которые можно вывести из начальной точки. Программа рискует не закончится в исторически обозримом времени. Я бы от него отказался.
Второй представляется более практичным. Он похож на поиск пути между двумя точками графа, где узлы - это пустые ячейки поля, а ребра - перемещения между ячейками. Поскольку у вас много пустот на поле, то представляется разумным применить поиск в ширину, где мы циклично отодвигаем грань поиска на один шаг, чтобы не блуждать в глубину по пустому полю.
Перепишем код, сделав его самодостаточным:
# needed for recursive type annotation in the Node class
from __future__ import annotations
WALL, EMPTY, START, GOAL = '# ST'
raw_grid = """
##################################################
# # T#
# # #
# # #
# # #
# # #
# # # #
# # # #
# # # #
# # # #
# # # #
# # # #
# # # #
# # # #
# # # #
# # # #
# # #
# # #
# # #
# # #
#S # #
##################################################
"""
grid = [*map(list, map(str.strip, raw_grid.strip().splitlines()))]
rows = len(grid)
columns = len(grid[0])
assert all(len(row) == columns for row in grid)
assert raw_grid.count(START) == raw_grid.count(GOAL) == 1
start_coords = divmod(raw_grid.index(START)-1, columns+1)
goal_coords = divmod(raw_grid.index(GOAL)-1, columns+1)
def print_field(field: list[list[str]]):
'''Pring the 2-dimentional character field to the console'''
print('\n'.join(map(''.join, field)))
def get_neighbours(x: int, y: int):
'''Return coordinates of cells adjacent to the left, right,
top, and bottom of the (x, y) point'''
for next_x, next_y in (x-1, y), (x+1, y), (x, y-1), (x, y+1):
if 0 <= next_x < rows and 0 <= next_y < columns:
yield next_x, next_y
class Node:
'''A tree node for connecting two consecutive
one-step wave propagations across the field'''
def __init__(self, coords: tuple[int, int], parent: Node | None = None):
self.coords = coords
self.parent = parent
def get_chain(self) -> list[tuple[int, int]]:
'''Return the coordinates of the chained cells,
starting from the current one up to the tree root'''
chain = []
node = self
while node is not None:
chain.append(node.coords)
node = node.parent
return chain
def BFS(start_coords: tuple[int, int], goal_coords: tuple[int, int]):
'''Breadth-first search'''
from collections import deque
visited = [[item == WALL for item in row] for row in grid]
queue = deque([Node(start_coords)])
x, y = start_coords
visited[x][y] = True
while queue:
node = queue.pop()
if node.coords == goal_coords:
return node.get_chain()
for x, y in get_neighbours(*node.coords):
if not visited[x][y]:
queue.appendleft(Node((x, y), node))
visited[x][y] = True
return None
chain = BFS(start_coords, goal_coords)
STEP = '⋅'
answer = grid.copy()
for x, y in chain[1:-1]:
answer[x][y] = STEP
print_field(answer)
Результат работы:
##################################################
# #⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅T#
# #⋅ #
# #⋅ #
# #⋅ #
#⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅ #⋅ #
#⋅ #⋅ #⋅ #
#⋅ #⋅ #⋅ #
#⋅ #⋅ #⋅ #
#⋅ #⋅ #⋅ #
#⋅ #⋅ #⋅ #
#⋅ #⋅ #⋅ #
#⋅ #⋅ #⋅ #
#⋅ #⋅ #⋅ #
#⋅ #⋅ #⋅ #
#⋅ #⋅ #⋅ #
#⋅ #⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅ #
#⋅ # #
#⋅ # #
#⋅ # #
#S # #
##################################################
P.S. Обобщенный подход к решению подобных задач из выступления Реймонда Хэтинджера