def longestIncreasingPath(matrix):

    if not matrix:

        return 0

    rows, cols = len(matrix), len(matrix[0])

    memo = [[0] * cols for _ in range(rows)]

    def dfs(row, col):

        if memo[row][col]:

            return memo[row][col]

        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        max_length = 1

        for dr, dc in directions:

            new_row, new_col = row + dr, col + dc

            if 0 <= new_row < rows and 0 <= new_col < cols and matrix[new_row][new_col] > matrix[row][col]:

                length = 1 + dfs(new_row, new_col)

                max_length = max(max_length, length)

        memo[row][col] = max_length

        return max_length

    longest_path = 0

    for i in range(rows):

        for j in range(cols):

            longest_path = max(longest_path, dfs(i, j))

    return longest_path

# Example usage:

matrix = [

    [9, 9, 4],

    [6, 6, 8],

    [2, 1, 1]

]

print(longestIncreasingPath(matrix))  # Output should be 4