Python递归实现矩阵中的最长递增路径问题

题目描述

给定一个n×n的矩阵，求出其中最长的递增路径的长度。可以走上下左右四个方向。

样例

输入：
[
[1,2,3,4],
[8,7,6,5],
[9,10,11,12],
[16,15,14,13]
]
输出：
12
解释：
最长递增路径为：1-2-3-4-5-6-7-8-9-10-11-12。

解题思路

这道题可以使用深度优先搜索（DFS）求解。我们可以以每个点作为起点，递归搜索它的四周。

在递归搜索的过程中，需要记录下当前访问的点的坐标和已经访问过的点的集合visited。若当前点坐标已经访问过，则直接返回visited中的值。

若当前点为递增路径的终点，则返回1。若当前点比上下左右四个方向的点都要小，则返回1。

若当前点比上下左右四个方向中的一个点大，则从四个方向中选择路径最长的那个，再加上当前点，作为当前路径的长度。

最终，遍历矩阵中的所有点，找到最长递增路径即可。

代码演示

下面是Python递归实现矩阵中的最长递增路径问题的代码：