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

问题内容：

我有一个2D数组，arr其中每个单元格的值分别为1、2或3 arr[0][0] = 3, arr[2][1] = 2, and arr[0][4] = 1。

我想知道从给定特定单元格arr[5][5]到最接近的单元格（其值为2）的最短路径，其中该路径不应包含任何具有值1的单元格。我该怎么做？

下面是BFS的脚本，但是如何使它接受2D数组作为图形，并将起点作为数组中某个单元格的位置，然后从该单元格转到最近的两个，避免使用1s的单元格，因此看起来像bfs(2darray, starting location, 2)什么？

def bfs(graph, start, end):
    # Maintain a queue of paths
    queue = []

    # Push the first path into the queue
    queue.append([start])
    while queue:

        # Get the first path from the queue
        path = queue.pop(0)

        # Get the last node from the path
        node = path[-1]

        # Path found
        if node == end:
            return path

        # Enumerate all adjacent nodes, construct a new path and push it into the queue
        for adjacent in graph.get(node, []):
            new_path = list(path)
            new_path.append(adjacent)
            queue.append(new_path)

print bfs(graph, '1', '11')

问题答案：

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

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, 5
grid = ["..........",
        "..*#...##.",
        "..##...#*.",
        ".....###..",
        "......*..."]
path = bfs(grid, (5, 2))
# [(5, 2), (4, 2), (4, 3), (4, 4), (5, 4), (6, 4)]

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

微信关注