python 中具有障碍 (0 ,1) 的矩阵中的最长路线

Question

问题是如何在0和1的矩阵中找到最长的路线

我们没有任何目的地和来源，我们必须找到矩阵中有 1 的最长可能路线

例如在下面的矩阵中，我们最长的路的长度是 8 :

1 0 0 1

1 1 1 1

0 1 0 1

或者在这个矩阵中，它是 6 :

0 0 0 1

1 1 0 0

0 1 0 0

1 1 1 1

我们如何在 python 中做到这一点？

Answer 1

现在，第一件事是定义一个函数，它将您要“探索”的矩阵和起点作为输入：
def take_a_step(matrix, pos=(0,0), available=None):
第三个 arg 应该是带有可用位置（尚未触及的点）的矩阵，或者第一次迭代的 None ；您也可以直接在参数中将其初始化为标准值，例如 True 的矩阵，但我更愿意在检查 None 之后在函数体中执行此操作，以便输入矩阵可以尺寸不同，不会引起不必要的问题。
所以它会变成这样：

    if(matrix[pos[0]][pos[1]]==0): 
        return 0 #out of path
    if(available is None):
        #list comprehension to make a new with same dim as the input
        available=[[True for i in range(len(matrix[0]))] for j in range(len(matrix))]
    for i in range(4):
        available[pos[0]][pos[1]]=False #remove current position from available ones
        newpos=pos #+something in each direction
        if(available[newpos[0]][newpos[1]]):
            take_a_step(matrix, newpos, available)
    #save the results for each route, use max()
    return maxres+1

显然代码需要检查和测试，可能有更有效的方法来做同样的事情，但它应该足以让你开始

python 中具有障碍 (0 ,1) 的矩阵中的最长路线

Longest route in a Matrix with hurdles (0 ,1) in python

python

python-3.x

longest-path