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

Question

The problem is how to find the longest route in a matrix of 0 and 1

We don't have any destination and source , We must find the longest possible route with 1 in matrix

For example in matrix below , the length of our longest way is 8 :

1 0 0 1

1 0 0 1

1 1 1 1

0 1 0 1

Or in this matrix , it's 6 :

0 0 0 1

1 1 0 0

0 1 0 0

1 1 1 1

How can we do that in python?

Answer 1

Now, the fist thing is to define a function which takes as input the matrix you want to "explore" and a starting point:
def take_a_step(matrix, pos=(0,0), available=None):
the third arg should be either a matrix with the available places (the points not touched yet), or None for the first iteration; you could also initialize it to a standard value like a matrix of Trues directly in the arguments, but I'd prefer to do it in the function body after checking for None so that the input matrix can be different sizes without causing unnecessary problems.
So it would come to something like:

    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

Obviously the code needs checking and testing, and there might be more efficient ways of doing the same thing, but it should be enough to let you start