पायथन में k विभिन्न रंगों के साथ बाड़ को पेंट करने के लिए न्यूनतम लागत खोजने का कार्यक्रम

मान लीजिए कि हम N बाड़ की एक पंक्ति को K के विभिन्न रंगों से रंगना चाहते हैं। हम यह सुनिश्चित करते हुए लागत को कम करना चाहते हैं कि कोई भी दो पड़ोसी बाड़ एक ही रंग के न हों। तो अगर हमारे पास एक एन एक्स के मैट्रिक्स है जहां nth पंक्ति और kth कॉलम nth बाड़ को kth रंग से पेंट करने की लागत का प्रतिनिधित्व करता है, तो हमें इस लक्ष्य को प्राप्त करने वाली न्यूनतम लागत का पता लगाना होगा।

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

तो आउटपुट 14 होगा, क्योंकि हम निम्नलिखित रंग सूचकांकों का चयन कर सकते हैं (पहली बाड़ से शुरू) - 5 → 2 → 3 → 4.

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

• n :=मैट्रिक्स की पंक्ति गणना

• fc :=0, ft :=0

• एससी:=1, सेंट:=0

• मैट्रिक्स में प्रत्येक पंक्ति के लिए, करें

  • एनएफसी:=-1, एनएफटी:=inf

  • एनएससी:=-1, एनएसटी:=inf

  • प्रत्येक अनुक्रमणिका i और मान t पंक्ति के लिए, करें

    • सीटी:=टी + (फीट अगर मैं एफसी के समान नहीं है अन्यथा सेंट)

    • अगर सीटी <=एनएफटी, तो

      • एनएससी:=एनएफसी, एनएसटी:=एनएफटी

      • एनएफसी:=मैं, एनएफटी:=सीटी

    • अन्यथा जब सीटी <=एनएसटी, तब

      • एनएससी:=मैं, एनएसटी:=सीटी

  • एफसी:=एनएफसी, फीट:=एनएफटी

  • एससी:=एनएससी, सेंट:=एनएसटी

• वापसी फुट

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

class Solution:
   def solve(self, matrix):
      n = len(matrix)
      fc, ft = 0, 0
      sc, st = 1, 0
      inf = int(1e18)
      for row in matrix:
         nfc, nft = -1, inf
         nsc, nst = -1, inf
         for i, t in enumerate(row):
            ct = t + (ft if i != fc else st)
            if ct <= nft:
               nsc, nst = nfc, nft
               nfc, nft = i, ct
            elif ct <= nst:
               nsc, nst = i, ct
         fc, ft = nfc, nft
         sc, st = nsc, nst
      return ft

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

इनपुट

[
   [6, 4, 5],
   [3, 2, 7],
   [3, 4, 5],
   [5, 4, 4]
]

आउटपुट

14