python - Python中连接两个坐标的多米诺骨牌路径

Question

上下文

我正在尝试创建一个迷宫解析器。

问题

是否可以对 [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]]

Answer 1

目前，解决我的问题的最佳方法是在这篇文章中找到的: Get shortest path to a cell in a 2d array 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)]