পাইথনে ম্যাট্রিক্সে সর্বোচ্চ দৈর্ঘ্যের স্ট্রিক্টলি ইনক্রিজিং পাথ খুঁজে বের করার প্রোগ্রাম

একটি ২D ম্যাট্রিক্স দেওয়া আছে। আমাদের এমন একটি পাথ খুঁজে বের করতে হবে যাতে প্রতিটি পরবর্তী সেলের মান পূর্ববর্তী সেলের চেয়ে বড় হয় (স্ট্রিক্টলি ইনক্রিজিং)। পাথে যাওয়ার সময় শুধু আপ, ডাউন, লেফট, রাইট—এই চার দিকেই যেতে পারব, ডায়াগোনালি যেতে পারব না।

উদাহরণস্বরূপ,

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

সর্বোচ্চ পাথ: [1, 2, 4, 6, 7, 9] → দৈর্ঘ্য ৬।

সমাধানের পদ্ধতি (DFS + মেমোরাইজেশন)

1. n, m = সারি ও কলাম সংখ্যা।
2. moves = [[1,0], [-1,0], [0,1], [0,-1]] (चार দিক)।
3. dp(y, x) ফাংশন ডিফাইন করুন যা (y,x) সেল থেকে শুরু করে সর্বোচ্চ ইনক্রিজিং পাথের দৈর্ঘ্য রিটার্ন করে।
   • যদি সেল ম্যাট্রিক্সের বাইরে পড়ে, ০ রিটার্ন করুন।
   • currVal = matrix[y][x]।
   • res = 0।
   • প্রতিটি মুভ (dy, dx) এর জন্য:
     • newY, newX = y+dy, x+dx।
     • যদি নতুন সেল বৈধ হয় এবং matrix[newY][newX] > currVal, তবে res = max(res, dp(newY, newX))।
   • return res + 1 (বর্তমান সেল যোগ করে)।
4. সকল সেল (i,j) থেকে dp(i,j) কল করে সর্বোচ্চ মান নিন।

পাইথন কোড উদাহরণ

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 dy, dx in moves:
                ny, nx = y + dy, x + dx
                if 0 <= ny < n and 0 <= nx < m and matrix[ny][nx] > currVal:
                    res = max(res, dp(ny, nx))
            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]]

আউটপুট

6