पायथन में दिए गए मैट्रिक्स में सबसे लंबे सख्ती से बढ़ते पथ की लंबाई खोजने का प्रोग्राम

मान लीजिए हमारे पास एक 2D मैट्रिक्स है, हमें सबसे लंबे सख्ती से बढ़ते पथ की लंबाई ढूंढनी है। पथ को पार करने के लिए हम ऊपर, नीचे, बाएं, या दाएं जा सकते हैं (तिरछे नहीं)।

उदाहरण के लिए, यदि इनपुट मैट्रिक्स है:

2	4	6
1	5	7
3	3	9

तो आउटपुट 6 होगा, क्योंकि सबसे लंबा पथ [1, 2, 4, 6, 7, 9] है।

समाधान दृष्टिकोण

इस समस्या को हल करने के लिए हम DFS + मेमोइजेशन का उपयोग करेंगे:

n := मैट्रिक्स की पंक्तियों की संख्या, m := कॉलम की संख्या
moves := चार दिशाओं के लिए पेयर्स की लिस्ट: [[1, 0], [-1, 0], [0, 1], [0, -1]]
dp(y, x) फंक्शन परिभाषित करें:
- यदि x और y मैट्रिक्स की रेंज में नहीं हैं, तो 0 लौटाएं
- currVal := matrix[y][x]
- res := 0
- moves में प्रत्येक d के लिए:
  - (dy, dx) := d
  - (newY, newX) := (y + dy, x + dx)
  - यदि newY और newX रेंज में हैं और matrix[newY][newX] > currVal है, तो res := max(res, dp(newY, newX))
- res + 1 लौटाएं
मुख्य मेथड में:
- result := 0
- सभी सेल्स (i, j) के लिए dp(i, j) कॉल करें और result अपडेट करें
- result लौटाएं

पायथन कार्यान्वयन

class Solution:
    def solve(self, matrix):
        n, m = len(matrix), len(matrix[0])
        moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        def dp(y, x):
            if y < 0 or y >= n or x < 0 or x >= m:
                return 0
            currVal = matrix[y][x]
            res = 0
            for d in moves:
                dy, dx = d
                newY, newX = y + dy, x + dx
                if (newY >= 0 and newY < n and newX >= 0 and newX < m and matrix[newY][newX] > currVal):
                    res = max(res, dp(newY, newX))
            return res + 1
        result = 0
        for i in range(n):
            for j in range(m):
                result = max(result, dp(i, j))
        return result

ob = Solution()
matrix = [
    [2, 4, 6],
    [1, 5, 7],
    [3, 3, 9]
]
print(ob.solve(matrix))

इनपुट

[ [2, 4, 6], [1, 5, 7], [3, 3, 9] ]