পাইথনে ম্যাট্রিক্স থেকে যেকোনো দিয়ে শুরু করে সর্বাধিক কয়েন সংগ্রহ

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

উদাহরণস্বরূপ, ম্যাট্রিক্স:

2	4	3
3	6	0
2	0	12

আউটপুট 18 (পথ: 2 → 3 → 6 → 4 → 3)।

সমাধানের ধাপসমূহ (ব্যাকট্র্যাকিং / DFS)

যদি ম্যাট্রিক্স খালি হয়, ০ রিটার্ন করুন।
n, m := সারি ও কলাম। x, y := দিকের অ্যারে ([-1,1,0,0], [0,0,-1,1])।
ok(a,b) ফাংশন: সেল ভ্যালিড কিনা এবং মান ০-র চেয়ে বড় কিনা চেক করে।
util(a,b) ফাংশন: বর্তমান সেল থেকে চার দিকে ট্রাই করে সর্বোচ্চ কয়েন বের করে (ব্যাকট্র্যাকিং: সেল ০ করে কল, পাশে রিস্টোর করে)।
প্রতিটি সেল (i,j) থেকে যদি মান ০-র চেয়ে বড় হয়, তবে সেটিকে ০ করে util(i,j) কল করুন এবং ফলাফল ম্যাক্সিমাইজ করুন।
সর্বোচ্চ ফলাফল রিটার্ন করুন।

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

class Solution:
    def solve(self, mat):
        if not mat:
            return 0
        n, m = len(mat), len(mat[0])
        x, y = [-1, 1, 0, 0], [0, 0, -1, 1]
        def ok(a, b):
            return 0 <= a < n and 0 <= b < m and mat[a][b]
        def util(a, b):
            ret = 0
            for k in range(4):
                t1, t2 = x[k] + a, y[k] + b
                if ok(t1, t2):
                    t, mat[t1][t2] = mat[t1][t2], 0
                    ret = max(ret, util(t1, t2) + t)
                    mat[t1][t2] = t
            return ret
        res = 0
        for i in range(n):
            for j in range(m):
                if mat[i][j]:
                    temp, mat[i][j] = mat[i][j], 0
                    res = max(res, util(i, j) + temp)
        return res

ob = Solution()
matrix = [[2, 4, 3], [3, 6, 0], [2, 0, 12]]
print(ob.solve(matrix))

ইনপুট

[[2, 4, 3], [3, 6, 0], [2, 0, 12]]