পাইথনে টার্গেট তৈরি করতে কলাম ফ্লিপ করার জন্য ন্যূনতম সংখ্যক অপারেশন গণনা করার প্রোগ্রাম

ধরুন আমাদের কাছে একই সংখ্যক সারি এবং কলাম সহ একটি ম্যাট্রিক্স M এবং একটি লক্ষ্য ম্যাট্রিক্স T রয়েছে। এখন ধরুন একটি অপারেশন যেখানে আমরা ম্যাট্রিক্সে একটি নির্দিষ্ট কলাম ফ্লিপ করি যাতে সমস্ত 1s 0s তে রূপান্তরিত হবে এবং সমস্ত 0s 1s তে রূপান্তরিত হবে। তাই যদি আমরা বিনামূল্যে ম্যাট্রিক্স সারিগুলিকে পুনরায় সাজাতে পারি, তাহলে M-কে T-এ পরিণত করার জন্য প্রয়োজনীয় ন্যূনতম সংখ্যক ক্রিয়াকলাপ খুঁজে বের করুন। যদি কোনো সমাধান না থাকে, তাহলে -1 ফেরত দিন।

সুতরাং, যদি ইনপুট M =

টি =

তারপর আউটপুট হবে 1, যেমন প্রথমে সারিগুলিকে-

এবং তারপর কলাম 1 থেকে -

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব−

• nums1 :=একটি নতুন তালিকা, nums2 :=একটি নতুন তালিকা

• ম্যাট্রিক্সের প্রতিটি সারির জন্য, করুন

  • ths :=0

  • সারি খালি না থাকার সময়, করুন

    • ths :=(ths*2) + সারি থেকে শেষ উপাদান, এবং সারির শেষ উপাদান মুছে দিন

  • nums1 এর শেষে ths ঢোকান

• লক্ষ্যের প্রতিটি সারির জন্য, করুন

  • ths :=0

  • যখন সারিটি শূন্য নয়, তখন করুন

  • ths :=(ths*2) + সারি থেকে শেষ উপাদান, এবং সারির শেষ উপাদান মুছে দিন

  • nums2 এর শেষে ths ঢোকান

• ret:=infinity

• nums1 এ প্রতিটি সংখ্যার জন্য করুন

  • cts :=সংখ্যা 1 এবং তাদের ফ্রিকোয়েন্সিতে স্বতন্ত্র উপাদান সহ একটি মানচিত্র

  • cts[num] :=cts[num] - 1

  • my_xor :=num XOR nums2[0>

  • আমি রেঞ্জ 1 থেকে সংখ্যা 2 এর আকারের জন্য, করুন

    • প্রয়োজন :=my_xor XOR nums2[i]

    • যদি cts[প্রয়োজনীয়] শূন্য হয়, তাহলে

      • লুপ থেকে বেরিয়ে আসুন

      • cts[প্রয়োজনীয়] :=cts[প্রয়োজনীয়] - 1

    • অন্যথায়,

    • ret:=ret এর সর্বনিম্ন, এবং my_xor এর সেট বিটের সংখ্যা

    • রিটার্ন ret যদি ret অসীম এর মত না হয় অন্যথায় -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