Longest Increasing Path in a Matrix

lcpy gen -n 329   # by problem number
lcpy gen -s longest_increasing_path_in_a_matrix   # by problem name

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4

Input: matrix = [[3,4,5],[3,2,6],[2,2,1]]
Output: 4

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

from functools import cache


class Solution:
    # Time: O(m * n)
    # Space: O(m * n)
    def longest_increasing_path(self, matrix: list[list[int]]) -> int:
        if not matrix or not matrix[0]:
            return 0

        rows, cols = len(matrix), len(matrix[0])
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        @cache
        def dfs(r: int, c: int) -> int:
            max_length = 1
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                    max_length = max(max_length, 1 + dfs(nr, nc))
            return max_length

        result = 0
        for i in range(rows):
            for j in range(cols):
                result = max(result, dfs(i, j))

        return result