Максимальное количество элементов на пути к матрице

Question

Я попытался решить проблему с картой (матрица 4x4) с помощью python.

Я хочу найти Максимальное количество элементов на пути к карте, если следующий узел должен быть меньше предыдущего узла со всеми возможными комбинациями элементов в матрице.

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

движение, как от элемента может перемещаться на восток-запад-север-юг

, например, из м [0] [1] может перейти в м [0] [2] и м [1] [1] 4-> 8 или 2

Вот пример кода, но я понятия не имею, как рекурсивно проверять каждый элемент.

#import itertools 
n = 4 
matrix = [[4, 8, 7, 3 ], [2, 5, 9, 3 ], [6, 3, 2, 5 ], [4, 4, 1, 6]] 
for index,ele in enumerate(matrix): 
    vals=[] 
    for i2,e2 in enumerate(ele): 
     for 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]) 

, как рекурсивный эту функцию в цикле до конца

Для примера ответом будет как 8-5-3-2-1 (самый длинный путь с уменьшением фактора)

Answer 1

Попробуйте это рекурсии: начиная Самый длинный путь в элементе (x, y) является самым длинным самый длинный путь, начиная с любого из его строго меньших соседей, плюс 1.

def longest_path(matrix): 
    def inner_longest_path(x, y): 
     best, best_path = 0, [] 
     # for all possible neighbor cells... 
     for dx, dy in ((+1, 0), (-1, 0), (0, +1), (0, -1)): 
      # if cell is valid and strictly smaller... 
      if (0 <= x + dx < len(matrix) and 0 <= y + dy < len(matrix[x]) 
        and matrix[x+dx][y+dy] < matrix[x][y]): 
       n, path = inner_longest_path(x+dx, y+dy) 
       # check if the path starting at that cell is better 
       if n > best: 
        best, best_path = n, path 
     return best + 1, [matrix[x][y]] + best_path 

    return max(inner_longest_path(x, y) for x, row in enumerate(matrix) 
             for y, _ in enumerate(row)) 

Обратите внимание, что это сделает много дублирующих расчетов. Добавление memoization остается как упражнение для читателя.

Пример:

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