पायथन में ऊपरी-बाएं से नीचे-दाएं सेल तक सिक्के चुनकर वापस आने का प्रोग्राम

मान लीजिए हमारे पास एक 2D मैट्रिक्स है जिसमें 3 संभावित मान हैं:

0 खाली सेल के लिए।
1 सिक्के के लिए।
-1 दीवार के लिए।

हमें ऊपरी-बाएं सेल से शुरू करके नीचे-दाएं सेल तक केवल दाएं या नीचे की दिशा में जाकर अधिकतम सिक्कों की संख्या ज्ञात करनी है। फिर केवल ऊपर या बाएं दिशा में चलकर ऊपरी-बाएं सेल पर वापस आना है। जब हम एक सिक्का उठाते हैं, तो सेल का मान 0 हो जाता है। यदि हम नीचे-दाएं सेल तक नहीं पहुंच सकते, तो 0 लौटाएं।

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

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

तो आउटपुट 8 होगा।

हल करने के चरण

n := mat की पंक्तियों की संख्या, m := mat के स्तंभों की संख्या
util() फ़ंक्शन परिभाषित करें। यह i, j, k, l लेगा
- यदि i और j, mat की रेंज में नहीं हैं या mat[i, j], -1 के समान है, तो -infinity लौटाएं
- यदि k और l, mat की रेंज में नहीं हैं या mat[k, l], -1 के समान है, तो -infinity लौटाएं
- यदि i, j, k और l सभी 0 हैं, तो mat[0, 0] लौटाएं
- best := -infinity
- प्रत्येक जोड़ी (dx1, dy1) के लिए [(-1, 0), (0, -1)] में, करें
  - प्रत्येक जोड़ी (dx2, dy2) के लिए [(-1, 0), (0, -1)] में, करें
    - best := best और util(i + dy1, j + dx1, k + dy2, l + dx2) का अधिकतम
- mat[i, j] + (1 जब i, k के समान नहीं है अन्यथा 0) * mat[k, l] + best लौटाएं
मुख्य विधि से निम्नलिखित करें:
- 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]]