```
class Solution(object):
def longestIncreasingPath(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: int
"""
if not matrix or len(matrix[0]) == 0: return 0
height, width = len(matrix), len(matrix[0])
paths = [[0] * width for _ in range(height)]
def dfs(r, c):
if paths[r][c] > 1:
return paths[r][c]
max_path = 1
# for next step (R, C) accessible from (r, c)
for R, C in [(r - 1, c), (r, c + 1), (r + 1, c), (r, c - 1)]:
if 0 <= R < height and 0 <= C < width:
if paths[r][c] > paths[R][C]: continue
if matrix[R][C] > matrix[r][c]:
max_path = max(max_path, dfs(R, C) + 1)
paths[r][c] = max_path
return max_path
res = max([dfs(r, c) for r in range(height) for c in range(width)])
return res
```