在Python中获取2D数组中单元格的最短路径

在Python中获取2D数组中单元格的最短路径

您可以对此进行简单的广度优先搜索。基本上，网格中的每个单元格都对应图中的一个节点，相邻单元格之间有边。从起始位置开始，并继续扩展可传递单元格，直到找到目标单元格为止。

def bfs(grid, start):    queue = collections.deque([[start]])    seen = set([start])    while queue:        path = queue.popleft()        x, y = path[-1]        if grid[y][x] == goal: return path        for x2, y2 in ((x+1,y), (x-1,y), (x,y+1), (x,y-1)): if 0 <= x2 < width and 0 <= y2 < height and grid[y2][x2] != wall and (x2, y2) not in seen:     queue.append(path + [(x2, y2)])     seen.add((x2, y2))

网格设置和结果：（请注意，我使用的是符号而不是数字，这仅仅是因为以这种方式在视觉上解析网格并验证解决方案更加容易。）

wall, clear, goal = "#", ".", "*"width, height = 10, 5grid = ["..........",        "..*#...##.",        "..##...#*.",        ".....###..",        "......*..."]path = bfs(grid, (5, 2))# [(5, 2), (4, 2), (4, 3), (4, 4), (5, 4), (6, 4)]