class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        M,N = len(matrix), len(matrix[0])
        directions = [(0,1),(0,-1),(1,0), (-1,0)]
        visited = {}
        
        def dfs(r,c):
            if (r,c) in visited: return visited[(r,c)]
            x = 1
            for i,j in directions:
                new_r, new_c = r+i, c+j
                if 0<=new_r<M and 0<=new_c<N and matrix[r][c]<matrix[new_r][new_c]:
                    x = max(x,dfs(new_r,new_c)+1)
            visited[(r,c)] = x
            return x
        
        output = 0
        for r in range(M):
            for c in range(N):
                output =max(output,dfs(r,c))
        return output
39f57247aedb1ab9a418e9a5dc755f8c80839f7c
<mask token>

class Solution:
    <mask token>

class Solution:

    def longestIncreasingPath(self, matrix: List[List[int]]) ->int:
        M, N = len(matrix), len(matrix[0])
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        visited = {}

        def dfs(r, c):
            if (r, c) in visited:
                return visited[r, c]
            x = 1
            for i, j in directions:
                new_r, new_c = r + i, c + j
                if 0 <= new_r < M and 0 <= new_c < N and matrix[r][c] < matrix[
                    new_r][new_c]:
                    x = max(x, dfs(new_r, new_c) + 1)
            visited[r, c] = x
            return x
        output = 0
        for r in range(M):
            for c in range(N):
                output = max(output, dfs(r, c))
        return output

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        M,N = len(matrix), len(matrix[0])
        directions = [(0,1),(0,-1),(1,0), (-1,0)]
        visited = {}
        
        def dfs(r,c):
            if (r,c) in visited: return visited[(r,c)]
            x = 1
            for i,j in directions:
                new_r, new_c = r+i, c+j
                if 0<=new_r<M and 0<=new_c<N and matrix[r][c]<matrix[new_r][new_c]:
                    x = max(x,dfs(new_r,new_c)+1)
            visited[(r,c)] = x
            return x
        
        output = 0
        for r in range(M):
            for c in range(N):
                output =max(output,dfs(r,c))
        return output