我有一个二维数组arr
,其中每个单元格都有一个值1、2或3,例如arr[0][0] = 3, arr[2][1] = 2 and arr[0][4] = 1
。我想知道从给定单元格(例如arr[5][5]
)到最近的值为2的单元格(其中路径不应包含任何值为1的单元格)的最短路径。有什么建议吗?
下面是BFS的脚本,但我不知道如何让它接受2d数组作为图形,并以数组中的某个单元格位置作为起始点,然后从该单元格到最近的2,避开1的单元格,使其看起来像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')
如果列表不太大,我找到的最简单的解决方案是使用numpy库的where函数来查找具有您要查找的值的单元格。因此,您需要将列表转换为numpy数组。
下面的代码可能会被简化,以使其更简短、更高效,但这样会更清楚。顺便说一下,您可以计算两种距离:典型的欧几里德距离和manhattan。
如果在与原始单元格相同的距离上有多个目标单元格,min_coords对应于找到的第一个单元格(先按行,然后按列)。
你可以用一个简单的breadth first search来完成这个。基本上,网格中的每个单元格都对应于图中的一个节点,相邻单元格之间有边。从起始位置开始,不断扩展可通过的单元格,直到找到目标单元格。
网格设置和结果:(请注意,我使用的是符号而不是数字,原因是这样更容易直观地分析网格并验证解决方案。)
相关问题 更多 >
编程相关推荐