पायथन में दिए गए मैट्रिक्स से अधिकतम सिक्के एकत्र करने का प्रोग्राम

मान लीजिए हमारे पास एक 2D मैट्रिक्स है जहां matrix[r, c] उस सेल में सिक्कों की संख्या दर्शाता है। हम किसी भी स्थिति से शुरू कर सकते हैं और चार दिशाओं (ऊपर, नीचे, बाएं और दाएं, विकर्ण नहीं) में से किसी में जाकर सिक्के एकत्र करना चाहते हैं। जब हम एक सेल पर जाते हैं तो सिक्के एकत्र हो जाते हैं और उस सेल का मान 0 हो जाता है। हम 0 सिक्कों वाले सेल पर नहीं जा सकते, हमें एकत्र किए जा सकने वाले अधिकतम सिक्कों की मात्रा ज्ञात करनी है।

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

तो आउटपुट 18 होगा, क्योंकि हम पथ 2 → 3 → 6 → 4 → 3 ले सकते हैं।

हल करने के चरण

• यदि मैट्रिक्स खाली है, तो 0 लौटाएं

• n := मैट्रिक्स की पंक्तियों की संख्या, m := mat के स्तंभों की संख्या

• x := [-1, 1, 0, 0] जैसी सूची, y := [0, 0, -1, 1] जैसी सूची

• util() फ़ंक्शन परिभाषित करें। यह a, b लेगा

  • ret := 0

  • k के लिए 0 से 3 तक की रेंज में, करें

    • (t1, t2) := (x[k] + a, y[k] + b)

    • यदि (t1, t2) वैध सेल है, तो

      • t := mat[t1, t2], mat[t1, t2] := 0

      • ret := ret और (util(t1, t2) + t) का अधिकतम

      • mat[t1, t2] := t

  • ret लौटाएं

• मुख्य विधि से निम्नलिखित करें:

  • res := 0

  • i के लिए 0 से n - 1 तक की रेंज में, करें

    • j के लिए 0 से m - 1 तक की रेंज में, करें

      • यदि mat[i, j] शून्येतर है, तो

        • t := mat[i, j], mat[i, j] := 0

        • res := res और (util(i, j) + temp) का अधिकतम

  • res लौटाएं

  उदाहरण

  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]]

  आउटपुट

  18