题目:
题解:
class Solution:DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]def longestIncreasingPath(self, matrix: List[List[int]]) -> int:if not matrix:return 0rows, columns = len(matrix), len(matrix[0])outdegrees = [[0] * columns for _ in range(rows)]queue = collections.deque()for i in range(rows):for j in range(columns):for dx, dy in Solution.DIRS:newRow, newColumn = i + dx, j + dyif 0 <= newRow < rows and 0 <= newColumn < columns and matrix[newRow][newColumn] > matrix[i][j]:outdegrees[i][j] += 1if outdegrees[i][j] == 0:queue.append((i, j))ans = 0while queue:ans += 1size = len(queue)for _ in range(size):row, column = queue.popleft()for dx, dy in Solution.DIRS:newRow, newColumn = row + dx, column + dyif 0 <= newRow < rows and 0 <= newColumn < columns and matrix[newRow][newColumn] < matrix[row][column]:outdegrees[newRow][newColumn] -= 1if outdegrees[newRow][newColumn] == 0:queue.append((newRow, newColumn))return ans