329. Longest Increasing Path in a Matrix 最長的路徑在矩陣裡面

 329. Longest Increasing Path in a Matrix 長的路徑在矩陣裡面

Given an m x n integers matrix, return the length of the longest increasing path in matrix.

From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).

 

Example 1:

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

Input: matrix = [[3,4,5],[3,2,6],[2,2,1]]
Output: 4
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Example 3:

Input: matrix = [[1]]
Output: 1

 

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 200
• 0 <= matrix[i][j] <= 231 - 1

最方便的做法就是用backtracking定義一個矩陣表示(a,b)當作終點 能走的最長路徑

如果算過 就重新走 從每個點出發 最後更新最大值

另一個看法是 把矩陣變成directed graph，兩點可從a到b 如果b比a大

這圖一定是acyclic directed graph

把每個weight當作-1

就變成shortest path of acyclic directed graph

可以用bfs解，複雜度大概是O(|V|^2) 應該是可以過

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        n = len(matrix)
        m = len(matrix[0])
        cache = [[0]*m for _ in range(n)]
        
        def is_valid(i, j):
            if 0 <= i < n and 0 <= j < m:
                return True
            return False
        
        def get_neighbors(i, j):
            neighbors = []
            for _i, _j in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
                if is_valid(_i, _j) and matrix[_i][_j] > matrix[i][j]:
                    neighbors.append((_i, _j))            
            return neighbors
                
        def backtrack(i, j):
            neighbors = get_neighbors(i, j)
            if not neighbors:
                if cache[i][j] == 0:
                    cache[i][j] = 1
            else:
                for _i, _j in neighbors:      
                    if cache[_i][_j] != 0:
                        cache[i][j] = max(cache[i][j], cache[_i][_j] + 1)
                    else:                    
                        cache[i][j] = max(cache[i][j], 1 + backtrack(_i, _j))
                    
            return cache[i][j]
        
        max_len = 1
        for i in range(n):
            for j in range(m):
                max_len = max(max_len, backtrack(i, j))
        
        return max_len