1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
class Solution:
max_len = 0
directions = {(1, 0), (-1, 0), (0, 1), (0, -1)}
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
if not matrix:
return 0
rows, cols = len(matrix), len(matrix[0])
record = [[0 for _ in range(cols)] for _ in range(rows)]
def dfs(i, j):
record[i][j] = 1
for direction in self.directions:
new_i, new_j = i + direction[0], j + direction[1]
if 0 <= new_i < rows and 0 <= new_j < cols and matrix[new_i][new_j] > matrix[i][j]:
if record[new_i][new_j] == 0:
dfs(new_i, new_j)
record[i][j] = max(record[i][j], record[new_i][new_j] + 1)
self.max_len = max(self.max_len, record[i][j])
for i in range(rows):
for j in range(cols):
if record[i][j] == 0:
dfs(i, j)
return self.max_len
|