पायथन में मैट्रिक्स में सबसे लंबा बढ़ता पथ

मान लीजिए हमारे पास एक मैट्रिक्स है; हमें सबसे लंबे बढ़ते पथ की लंबाई ढूंढनी है। प्रत्येक सेल से, हम चार दिशाओं में जा सकते हैं - बाएं, दाएं, ऊपर या नीचे। हम विकर्ण रूप से नहीं जा सकते या सीमा के बाहर नहीं जा सकते।

इसलिए, यदि इनपुट इस तरह है

तो आउटपुट 4 होगा क्योंकि सबसे लंबा बढ़ता पथ [3, 4, 5, 6] है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• solve() फ़ंक्शन परिभाषित करें। यह i, j, matrix लेगा

• यदि dp[i,j] शून्येतर है, तो

  • dp[i, j] लौटाएं

• dp[i, j] := 1

• temp := 0

• r को i-1 से i+2 तक की रेंज में, करें

  • c को j-1 से j+2 तक की रेंज में, करें

    • यदि r, i के समान है और c, j के समान है या (|r-i|, 1 के समान है और |c-j|, 1 के समान है), तो

      • अगले पुनरावृत्ति के लिए जाएं

    • यदि c>=0 और r>=0 और r < मैट्रिक्स की पंक्ति संख्या और c < मैट्रिक्स[0] का कॉलम आकार और matrix[r, c] > matrix[i, j], तो

      • temp := temp, solve(r, c, matrix) का अधिकतम

• dp[i, j] := dp[i, j] + temp

• dp[i, j] लौटाएं

• मुख्य मेथड से निम्नलिखित करें -

• यदि मैट्रिक्स शून्येतर नहीं है, तो

  • 0 लौटाएं

• dp := दी गई मैट्रिक्स के आकार का एक मैट्रिक्स बनाएं और 0 से भरें

• ans := 0

• i को 0 से मैट्रिक्स के आकार तक की रेंज में, करें

  • j को 0 से मैट्रिक्स[0] के आकार तक की रेंज में, करें

    • यदि dp[i, j] 0 के समान है, तो

      • solve(i, j, matrix)

• ans लौटाएं

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -

class Solution(object):     def solve(self, i, j, matrix):         if self.dp[i][j]:             return self.dp[i][j]         self.dp[i][j] = 1         temp = 0         for r in range(i-1, i+2):             for c in range(j-1, j+2):                 if r == i and c == j or (abs(r-i) == 1 and abs(c-j) == 1):                     continue                 if c >= 0 and r >= 0 and r < len(matrix) and c < len(matrix[0]) and matrix[r][c] > matrix[i][j]:                     temp = max(temp, self.solve(r, c, matrix))         self.dp[i][j] += temp         return self.dp[i][j]     def longestIncreasingPath(self, matrix):         if not matrix:             return 0         self.dp = [[0 for i in range(len(matrix[0]))] for j in range(len(matrix))]         self.ans = 0         for i in range(len(matrix)):             for j in range(len(matrix[0])):                 if self.dp[i][j] == 0:                     self.solve(i, j, matrix)                 self.ans = max(self.ans, self.dp[i][j])         return self.ans ob = Solution() print(ob.longestIncreasingPath([[9, 9, 4], [6, 6, 8], [2, 1, 1]]))

इनपुट

[[9, 9, 4], [6, 6, 8], [2, 1, 1]]

आउटपुट

4