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

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

• 0 खाली सेल के लिए।

• 1 सिक्के के लिए।

• -1 दीवार के लिए।

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

तो, अगर इनपुट पसंद है

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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• n :=चटाई की पंक्ति संख्या, m :=चटाई की स्तंभ संख्या

• उपयोग() फ़ंक्शन को परिभाषित करें। इसमें i, j, k, l

  . लगेगा

• यदि i और j चटाई या चटाई की सीमा में नहीं हैं [i, j] −1 के समान है, तो

  • वापसी -inf

• यदि k और l चटाई या चटाई की सीमा में नहीं हैं [k, l] −1 के समान है, तो

  • वापसी -inf

• अगर i, j, k और l सभी 0 हैं, तो

  • वापसी चटाई[0, 0]

• सर्वोत्तम:=-इन्फ़

• [(−1, 0) ,(0, −1)] में प्रत्येक जोड़ी (dx1, dy1) के लिए, करें

  • [(−1, 0) ,(0, −1)] में प्रत्येक जोड़ी (dx2, dy2) के लिए, करें

    • सर्वोत्तम:=अधिकतम सर्वोत्तम और उपयोग (i + dy1, j + dx1, k + dy2, l + dx2)

• वापसी चटाई [i, j] +(1 जब मैं कश्मीर के समान नहीं है, अन्यथा 0) * चटाई [के, एल] + सबसे अच्छा

• मुख्य विधि से निम्न कार्य करें -

• अधिकतम 0 लौटाएं और उपयोग करें(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]
]

आउटपुट

8