我试图使用python解决地图(矩阵4x4)的问题.
I tried to solve a problem of map (matrix 4x4) using python.
如果矩阵中所有可能的元素组合，下一个节点必须小于前一个节点，我想找到地图路径中的最大元素数.
I want to find Maximum number of elements in the path of a map provided the next node must be lesser than the previous node with all possible combinations of elements in the matrix.
4 8 7 3 2 5 9 3 6 3 2 5 4 4 1 6运动就像是从一个元素可以移动到东西南北
The movement is like from an element can move to east-west-north-south
例如从m [0] [1]可以移至m [0] [2]和m [1] [1] 4-> 8或2
For example from m[0][1] can move to m[0][2] and m[1][1] 4-> 8 or 2
这是示例代码，但我不知道如何递归检查每个元素.
Here is the sample code but i have no idea to how to 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]] 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])如何递归此函数以循环直至结束
how to recurse this function to loop till the end
例如，答案将类似于8-5-3-2-1(系数减小的最长路径)
For Example the answer will be like 8-5-3-2-1 (Longest Path with decreasing factor)
推荐答案尝试此递归:从元素(x, y)开始的最长路径是最长的最长路径，从其任何严格较小的邻居开始，再加上1.
Try this recursion: The longest path starting at element (x, y) is the longest longest path starting at any of its strictly smaller neighbors, plus 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))请注意，这将进行大量重复的计算.随便给读者增添便笺的内容.
Note that this will do a lot of duplicate calculations. Adding memoization is left as an excercise to the reader.
示例:
>>> longest_path(matrix) (5, [9, 5, 3, 2, 1])