python - 如果矩阵中有 3 个可能的值，如何找到最短路径？

Question

我试图找到以下问题的算法，但无法获得完整的解决方案。

在一个大小为 (100,100) 的矩阵中，每个值可以是 -- 0 - 打开，1 - 阻止，2 - 用金币打开，

矩阵中的金币数量可以在 0 到 10 之间。

A 位于起始位置 (0,0)，B 位于矩阵中的位置 (m,n)。

任务是找到 A 可以遵循的最短路径来收集所有金币并将它们交付给 B。A 可以移动北、南、东或西。

下面是我试过的代码（迷宫是矩阵，B是B的位置）--

def democode(maze, B):
 #with some initialization over here 
  while len(queue) != 0:
    i,j=queue.pop(0)
    result+=1 
    for m,n in getneighbors(i,j):
        if (0<=m<rows) and (0<=n<cols):
            if m == B[0] and n == B[1]:
                break
            if maze[m][n] != 1 and visited[m][n] == 0:
                queue.append((m,n))
                visited[m][n] = 1

return result

该解决方案没有考虑确保 A 在到达 B 之前收集所有金币的问题。需要一些改进此代码以涵盖所有场景的建议。

标签： pythonalgorithmpython-2.7matrixmaze