পাইথনে উপরের বাম থেকে নিচের ডান কোণে যেনা-আসেনায় সর্বাধিক কয়েন সংগ্রহ

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

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

0	1	1
1	1	1
1	-1	1
0	1	1

আউটপুট হবে 8।

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

n, m := সারি ও কলাম সংখ্যা।
util(i, j, k, l) ফাংশন ডিফাইন করুন যা দুটি পথ (i,j) এবং (k,l) থেকে একসাথে রিকার্সন করবে।
বেস কেস: আউট অফ বাউন্ড বা দেওয়াল হলে -∞ রিটার্ন। (0,0,0,0) হলে mat[0][0] রিটার্ন।
প্রতিটি মুভ কম্বিনেশন ((-1,0), (0,-1)) × ((-1,0), (0,-1)) এর জন্য রিকার্সিভ কল দিয়ে best আপডেট করুন।
রিটার্ন: mat[i][j] + (i!=k)*mat[k][l] + best
মেইন থেকে max(0, util(n-1, m-1, n-1, m-1)) রিটার্ন করুন।

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

class Solution:
    def solve(self, mat):
        n, m = len(mat), len(mat[0])
        def util(i, j, k, l):
            if not (0 <= i < n and 0 <= j < m) or mat[i][j] == -1:
                return -1e9
            if not (0 <= k < n and 0 <= l < m) or mat[k][l] == -1:
                return -1e9
            if i == 0 and j == 0 and k == 0 and l == 0:
                return mat[0][0]
            best = -1e9
            for dx1, dy1 in [(-1, 0), (0, -1)]:
                for dx2, dy2 in [(-1, 0), (0, -1)]:
                    best = max(best, util(i + dy1, j + dx1, k + dy2, l + dx2))
            return mat[i][j] + (i != k) * mat[k][l] + best
        return max(0, util(n - 1, m - 1, n - 1, m - 1))

ob = Solution()
matrix = [
    [0, 1, 1],
    [1, 1, 1],
    [1, -1, 1],
    [0, 1, 1]
]
print(ob.solve(matrix))

ইনপুট

[[0, 1, 1], [1, 1, 1], [1, -1, 1], [0, 1, 1]]