Домино путь, соединяющий две координаты в Python - PullRequest
Новая
       24

Домино путь, соединяющий две координаты в Python

1 голос
/ 16 января 2020

Контекст

Я пытаюсь создать распознаватель лабиринта.

maze

Вопрос

Это можно отсортировать и отфильтровать список [x, y] координат, более или менее похожих на домино, соединяющих 2 известные координаты?

Вход 

# [2, 2] is start
# [6, 2] is end
[[2, 2], [4, 2], [5, 2], [2, 3], [4, 3], [2, 4], [3, 4], [4, 4], [2, 5], [4, 5], [5, 5], [6, 2]]

Требуемый вывод 

# Shortest path from Start to End
[[2, 2], [2, 3], [2, 4], [3, 4], [4, 4], [4, 3], [4, 2], [5, 2], [6, 2]]

1 Ответ

0 голосов
/ 23 января 2020

На данный момент лучший способ решить мою проблему был найден в этом сообщении: Получить кратчайший путь к ячейке в массиве 2d python

Вот способ, который я использовал данный код. Работает отлично: 

import collections

start = (2, 2)
end = (6, 2)
grid = [(2, 2), (4, 2), (5, 2), (2, 3), (4, 3), (2, 4), (3, 4), (4, 4), (2, 5), (4, 5), (5, 5), (6, 2)]

queue = collections.deque([[start]])
seen = set(start)

while queue:
    path = queue.popleft()
        (x, y) = path[-1]
        if (x, y) == end:
            return path
        for x2, y2 in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):
            if (x2, y2) not in seen and (x2, y2) in grid:
                queue.append(path + [(x2, y2)])
                seen.add((x2, y2)) 
print(path)
# path is [(2, 2), (2, 3), (2, 4), (3, 4), (4, 4), (4, 3), (4, 2), (5, 2), (6, 2)]
...