python - Maximum number of elements in the path of a matrix -

i tried solve problem of map (matrix 4x4) using python.

i want find maximum number of elements in path of map provided next node must lesser previous node possible combinations of elements in matrix.

4 8 7 3   2 5 9 3   6 3 2 5   4 4 1 6   

the movement element can move east-west-north-south

for example m[0][1] can move m[0][2] , m[1][1] 4-> 8 or 2

here sample code have no idea how recursively check every element.

#import itertools n = 4  matrix = [[4, 8, 7, 3 ], [2, 5, 9, 3 ], [6, 3, 2, 5 ], [4, 4, 1, 6]] index,ele in enumerate(matrix):     vals=[]     i2,e2 in enumerate(ele):         index2,ele2 in enumerate(ele):             if index < (n-1):                 if ele2 > matrix[index+1] [index2]:                     vals.append(matrix[index+1] [index2])             if index > 0:                 if ele2 > matrix[index-1] [index2]:                     vals.append(matrix[index-1] [index2])             if index2 < n-1:                 if ele2 > matrix[index] [index2+1]:                     vals.append(matrix[index] [index2+1])             if index2 >0:                 if ele2 > matrix[index] [index2-1]:                     vals.append(matrix[index] [index2-1]) 

how recurse function loop till end

for example answer 8-5-3-2-1 (longest path decreasing factor)

try recursion: longest path starting @ element (x, y) longest longest path starting @ of strictly smaller neighbors, plus 1.

def longest_path(matrix):     def inner_longest_path(x, y):         best, best_path = 0, []         # possible neighbor cells...         dx, dy in ((+1, 0), (-1, 0), (0, +1), (0, -1)):             # if cell valid , strictly smaller...             if (0 <= x + dx < len(matrix) , 0 <= y + dy < len(matrix[x])                      , matrix[x+dx][y+dy] < matrix[x][y]):                 n, path = inner_longest_path(x+dx, y+dy)                 # check if path starting @ cell better                 if n > best:                     best, best_path = n, path         return best + 1, [matrix[x][y]] + best_path      return max(inner_longest_path(x, y) x, row in enumerate(matrix)                                          y, _ in enumerate(row)) 

note lot of duplicate calculations. adding memoization left excercise reader.

example:

>>> longest_path(matrix) (5, [9, 5, 3, 2, 1])