我有一个二维数组，arr，其中每个单元格的值都是 1、2 或 3，例如，arr[0][0] = 3, arr[ 2][1] = 2，并且 arr[0][4] = 1。
我想知道从给定的特定单元格(例如 arr[5][5])到最近单元格的最短路径，该单元格的值为 2，路径不应包含任何单元格值为 1。我该怎么做？
下面是 BFS 的脚本，但是我怎样才能让它接受一个二维数组作为图形，并将起点作为数组中某个单元格的位置，然后从这个单元格转到最近的两个，避免使用 1s 的单元格，这样它看起来像 bfs( 2darray，起始位置，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')
请您参考如下方法:
您可以使用简单的 breadth first search为了这。基本上，网格中的每个单元格对应于图中的一个节点，相邻单元格之间有边。从起始位置开始，不断扩展可通过的单元格，直到找到目标单元格。
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)]
