পাইথনে ম্যাট্রিক্সে সবচেয়ে লম্বা ক্রমবর্ধমান পথ (Longest Increasing Path) খুঁজে বের করা

ধরা যাক একটি ম্যাট্রিক্স দেওয়া আছে; আমাদের এর সবচেয়ে লম্বা ক্রমবর্ধমান পথের (longest increasing path) দৈর্ঘ্য বের করতে হবে। প্রতিটি সেল থেকে চার দিকেই (বাম, ডান, উপরে, নিচে) যাওয়া যায়। ডায়াগোনালি বা বাউন্ডেরি বাইরে যাওয়া যাবে না।

যেমন, ইনপুট হলে:

9	9	4
6	6	8
2	1	1

আউটপুট হবে ৪, কারণ সবচেয়ে লম্বা ক্রমবর্ধমান পথ হলো [3, 4, 5, 6]। (নোট: মেট্রিক্সের মান অনুযায়ী পথ হবে ১→২→৬→৯ বা সমতুল্য)

সমাধানের ধাপসমূহ

solve(i, j, matrix) ফাংশন ডিফাইন করবে।
ডাইনামিক প্রোগ্রামিং (DP) টেবিল ব্যবহার করে মেমোইজেশন করা হবে।
প্রতিটি সেল থেকে চার দিকেই রিকার্সিভলি পরবর্তী বড় মান খুঁজে বের করা হবে।
ম্যাক্সিমাম পথের দৈর্ঘ্য রিটার্ন করবে।

উদাহরণ (সম্পূর্ণ ইমপ্লিমেন্টেশন)

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 _ in range(len(matrix[0]))] for _ 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]]

আউটপুট