पायथन में लक्ष्य बनाने के लिए कॉलम फ्लिप करने के लिए न्यूनतम संख्या में संचालन की गणना करने का कार्यक्रम

मान लीजिए कि हमारे पास समान पंक्तियों और स्तंभों के साथ एक मैट्रिक्स M और एक लक्ष्य मैट्रिक्स T है। अब मान लीजिए एक ऑपरेशन जहां हम मैट्रिक्स में एक विशेष कॉलम को फ्लिप करते हैं ताकि सभी 1s को 0s में बदल दिया जाए और सभी 0s को 1s में बदल दिया जाए। इसलिए यदि हम मैट्रिक्स पंक्तियों को मुफ्त में पुन:व्यवस्थित कर सकते हैं, तो M को T में बदलने के लिए आवश्यक न्यूनतम संख्या में ऑपरेशन खोजें। यदि कोई समाधान नहीं है, तो -1 लौटाएं।

इसलिए, यदि इनपुट M =

टी =

तब आउटपुट 1 होगा, क्योंकि पहले पंक्तियों को-

और फिर कॉलम 1 को-

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

• nums1 :=एक नई सूची, nums2 :=एक नई सूची

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

  • वें :=0

  • जबकि पंक्ति खाली नहीं है, करें

    • ths :=(ths*2) + पंक्ति से अंतिम तत्व, और पंक्ति के अंतिम तत्व को हटा दें

  • nums1 के अंत में ths डालें

• लक्ष्य में प्रत्येक पंक्ति के लिए, करें

  • वें :=0

  • जबकि पंक्ति शून्य नहीं है, करें

  • ths :=(ths*2) + पंक्ति से अंतिम तत्व, और पंक्ति के अंतिम तत्व को हटा दें

  • nums2 के अंत में ths डालें

• रिट:=अनंत

• nums1 में प्रत्येक अंक के लिए, करें

  • cts :=nums1 में अलग-अलग तत्वों और उनकी आवृत्तियों के साथ एक नक्शा

  • सीटीएस [संख्या]:=सीटी [संख्या] - 1

  • my_xor :=num XOR nums2[0]

  • मैं के लिए 1 से लेकर nums2 के आकार तक, करें

    • आवश्यक :=my_xor XOR nums2[i]

    • अगर cts[needed] शून्य है, तो

      • लूप से बाहर आएं

      • सीटीएस [आवश्यक]:=सीटी [आवश्यक] - 1

    • अन्यथा,

    • ret:=न्यूनतम रिट, और my_xor के सेट बिट की संख्या

    • रिटर्न रिट अगर रिट इन्फिनिटी के समान नहीं है अन्यथा -1

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

उदाहरण

class Solution:
   def solve(self, matrix, target):
      nums1 = []
      nums2 = []
      for row in matrix:
         ths = 0
         while row:
            ths = (ths<<1) + row.pop()
         nums1.append(ths)
      for row in target:
         ths = 0
         while row:
            ths = (ths<<1) + row.pop()
         nums2.append(ths)
      ret=float('inf')
      from collections import Counter
      for num in nums1:
         cts = Counter(nums1)
         cts[num] -= 1
         my_xor = num^nums2[0]
         for i in range(1,len(nums2)):
            needed = my_xor^nums2[i]
            if not cts[needed]:
               break
            cts[needed]-=1
         else:
            ret=min(ret,bin(my_xor).count('1'))
      return ret if ret!=float('inf') else -1
ob = Solution()
M = [
   [0, 0],
   [1, 0],
   [1, 1]
]
T = [
   [0, 1],
   [1, 0],
   [1, 1]
]
print(ob.solve(M,T))

इनपुट

M = [[0, 0],[1, 0],[1, 1]] T = [[0, 1],[1, 0],[1, 1]]

आउटपुट

1