পাইথনে ম্যাট্রিক্সের খালি সেল N টি বেছে নেওয়ার কতভাবে আছে তা চেক করার প্রোগ্রাম

ধরি আমাদের একটি N x N বাইনারি ম্যাট্রিক্স আছে যেখানে ০ খালি সেল এবং ১ ব্লকড সেল। আমাদের N টি খালি সেল বেছে নেওয়ার উপায়ের সংখ্যা বের করতে হবে যাতে প্রতিটি সারি এবং প্রতিটি কলামে কমপক্ষে একটি বেছে নেওয়া সেল থাকে। যদি উত্তর খুব বড় হয় তবে রেজাল্ট মড ১০^৯ + ৭ রিটার্ন করুন।

তাই, ইনপুট যদি নিচের ম্যাট্রিক্স হয়, তবে আউটপুট হবে ৪, কারণ নিচের কনফিগারেশনগুলো আছে (যেখানে x হলো সিলেক্টেড সেল):

সমাধানের ধাপগুলো:

• n := ম্যাট্রিক্সের সাইজ
• f() ফাংশন ডিফাইন করুন। এটি i, bs নিবে
• যদি i >= n, তবে
  • ১ রিটার্ন করুন
• ans := 0
• j = ০ থেকে n পর্যন্ত, করুন
  • যদি matrix[i, j] == 0 এবং (2^j AND bs) == 0, তবে
    • ans := ans + f(i + 1, bs OR 2^j)
• ans রিটার্ন করুন
• মেইন মেথড থেকে f(0, 0) কল করে রিটার্ন করুন

বেশি বুঝতে নিচের বাস্তবায়নটি দেখুন:

উদাহরণ

class Solution:
    def solve(self, matrix):
        n = len(matrix)
        def f(i, bs):
            if i >= n:
                return 1
            ans = 0
            for j in range(n):
                if matrix[i][j] == 0 and ((1 << j) & bs == 0):
                    ans += f(i + 1, bs | (1 << j))
            return ans
        return f(0, 0)

ob = Solution()
matrix = [
    [0, 0, 0],
    [0, 0, 0],
    [0, 1, 0]
]
print(ob.solve(matrix))

ইনপুট

[[0, 0, 0], [0, 0, 0], [0, 1, 0]]

আউটপুট

4