Участник:Mugadzhir/longest-increasing-path-in-a-matrix

Материал из DISCOPAL
Перейти к: навигация, поиск
class Solution:
	def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
		directions=[(-1,0),(0,1),(1,0),(0,-1)]
		if not matrix:return 0
		m,n=len(matrix),len(matrix[0])
		def check(x,y): #boundary check
			return x>=0 and x<m and y>=0 and y<n
		import functools
		@functools.lru_cache(None)
		def dfs(x,y):
			length,max_length=1,1
			for direction in directions:
				nx,ny=x+direction[0],y+direction[1]
				if check(nx,ny) and matrix[nx][ny]>matrix[x][y]:
					length = 1 + dfs(nx,ny)
				max_length=max(length,max_length)
			return max_length
		res=0
		for i in range(m):
			for j in range(n):
				x=dfs(i,j)
				res=max(res,x)
		return res