给定一个二维数组matrix,可以从任何位置出发,每一步可以走向上、下、左、右,四个方向。返回最大递增链的长度。

区块链毕设网qklbishe.com为您提供问题的解答

给定一个二维数组matrix,可以从任何位置出发,每一步可以走向上、下、左、右,四个方向。返回最大递增链的长度。

def longestIncreacingPath(matrix):     n = len(matrix)     if n==0:         return 0     m = len(matrix[0])     dp = [[0]*m for _ in range(n)]      def dfs(x,y):         if dp[x][y]!=0:             return dp[x][y]         next = [[-1,0],[1,0],[0,-1],[0,1]]         ans = 0         for i in range(4):             tx = x + next[i][0]             ty = y + next[i][1]             if tx<0&nbs***bsp;ty<0&nbs***bsp;tx>=n&nbs***bsp;ty>=m: # 超出范围                 continue             if matrix[x][y]>=matrix[tx][ty]:   # 不满足递增                 continue             ans = max(ans,dfs(tx,ty))          # 否则就找四个方向中最长的         ans += 1        # 加上他自己         dp[x][y] = ans  # 备忘录         return ans      res = 0     for i in range(n):         for j in range(m):             res = max(res,dfs(i,j))     return res  row ,col = list(map(int,input().split(' '))) arr =[] for _ in range(row):     arr.append(list(map(int,input().split(' '))))  print(longestIncreacingPath(arr)) 

一个带备忘录的dfs,能全过

24:29

以上就是关于问题给定一个二维数组matrix,可以从任何位置出发,每一步可以走向上、下、左、右,四个方向。返回最大递增链的长度。的答案

欢迎关注区块链毕设网-
专业区块链毕业设计成品源码,定制。

区块链NFT链游项目方科学家脚本开发培训

承接区块链项目定制开发

微信:btc9767

QQ :1330797917

TELEGRAM: BTCOK9

承接区块链项目定制开发


qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台-javagopython毕设 » 给定一个二维数组matrix,可以从任何位置出发,每一步可以走向上、下、左、右,四个方向。返回最大递增链的长度。

发表评论