Python Solution


  • 0
    S
    class Solution(object):
        def longestIncreasingPath(self, matrix):
            """
            :type matrix: List[List[int]]
            :rtype: int
            """
            if not matrix or len(matrix[0]) == 0: return 0
            height, width = len(matrix), len(matrix[0])
    
            paths = [[0] * width for _ in range(height)]
    
            def dfs(r, c):
                if paths[r][c] > 1:
                    return paths[r][c]
    
                max_path = 1
    
                # for next step (R, C) accessible from (r, c)
                for R, C in [(r - 1, c), (r, c + 1), (r + 1, c), (r, c - 1)]:
                    if 0 <= R < height and 0 <= C < width:
                        if paths[r][c] > paths[R][C]: continue
                        if matrix[R][C] > matrix[r][c]:
                            max_path = max(max_path, dfs(R, C) + 1)
    
                paths[r][c] = max_path
    
                return max_path
    
            res = max([dfs(r, c) for r in range(height) for c in range(width)])
    
            return res

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.