class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
      @functools.lru_cache(None)
      def helper(x,y,r,c):
        cur = matrix[x][y]
        dises = [1]
        for d in dirs:
          cx = x + d[0]
          cy = y + d[1]
          if cx >= 0 and cx < r and cy >= 0 and cy < c:
            if matrix[cx][cy] > cur:
              dises.append(helper(cx,cy,r,c)+1)
        return max(dises)

      dirs = [(0,1),(0,-1),(-1,0),(1,0)]
      if matrix == []:
        return 0

      r = len(matrix)
      c = len(matrix[0])
      dis = 0
      for i in range(r):
        for j in range(c):
          dis = max(dis,helper(i,j,r,c))
      return dis