Участник: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(mat…»)
Строка 1: Строка 1:
class Solution:
+
* https://leetcode.com/problems/longest-increasing-path-in-a-matrix/
 +
<code-python>
 +
class Solution:
 
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
 
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
 
directions=[(-1,0),(0,1),(1,0),(0,-1)]
 
directions=[(-1,0),(0,1),(1,0),(0,-1)]
Строка 22: Строка 24:
 
res=max(res,x)
 
res=max(res,x)
 
return res
 
return res
 +
</code-python>
  
 
[[Категория:На проверку]]
 
[[Категория:На проверку]]

Версия 22:52, 25 мая 2020

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