矩阵最长递增路径

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 递增路径的最大长度
# @param matrix int整型二维数组 描述矩阵的每个数
# @return int整型
#
class Solution:
    def solve(self , mat: List[List[int]]) -> int:
        # write code here
        dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        def dfs(i, j):
            if memo[i][j] > 0 : return memo[i][j]
            memo[i][j] = 1
            for dir in dirs:
                x, y = i + dir[0], j + dir[1]
                if x < 0&nbs***bsp;x >= len(mat)&nbs***bsp;y < 0&nbs***bsp;y >= len(mat[0])&nbs***bsp;mat[x][y] <= mat[i][j]: continue
                memo[i][j] = max(memo[i][j], dfs(x, y) + 1)
            return memo[i][j]
        m, n, ans = len(mat), len(mat[0]), 0
        memo = [[0] * n for _ in range(m)] 
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                ans = max(ans, dfs(i, j))
        return ans

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 递增路径的最大长度
# @param matrix int整型二维数组 描述矩阵的每个数
# @return int整型
#
class Solution:
    def maxDist(self, matrix: List[List[int]], dist: List[List[int]], x: int, y: int):
        left, right, down, up = 0, 0, 0, 0
        if dist[x][y] > 0:
            return dist[x][y]
        if y > 0 and matrix[x][y] < matrix[x][y-1]:
            left = self.maxDist(matrix, dist, x, y-1) + 1
        if y < len(dist[0]) - 1 and matrix[x][y] < matrix[x][y + 1]:
            right = self.maxDist(matrix, dist, x, y+1) + 1
        if x > 0 and matrix[x][y] < matrix[x-1][y]:
            up = self.maxDist(matrix, dist, x-1, y) + 1
        if x < len(dist) - 1 and matrix[x][y] < matrix[x+1][y]:
            down = self.maxDist(matrix, dist, x+1, y) + 1
        dist[x][y] = max(left, right, down, up, 1)
        return dist[x][y]

    def solve(self , matrix: List[List[int]]) -> int:
        row, col = len(matrix), len(matrix[0])
        dist = [[0]*col for _ in range(row)]
        ret = 0
        for i in range(row):
            for j in range(col):
                if dist[i][j] == 0:
                    self.maxDist(matrix, dist, i, j)
                ret = max(ret, dist[i][j])
        return ret