मान लीजिए हमारे पास एक N x N बाइनरी मैट्रिक्स है जहां 0 खाली सेल के लिए है और 1 ब्लॉक्ड सेल है, हमें N खाली सेल चुनने के तरीकों की संख्या ढूंढनी है ताकि हर पंक्ति और हर कॉलम में कम से कम एक चुना हुआ सेल हो। यदि उत्तर बहुत बड़ा है तो परिणाम mod 10^9 + 7 लौटाएं
इसलिए, यदि इनपुट इस तरह है
| 0 | 0 | 0 |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
तो आउटपुट 4 होगा, क्योंकि हमारे पास निम्नलिखित कॉन्फिगरेशन हैं (जहां x एक चुना हुआ सेल है) -

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- n := मैट्रिक्स का आकार
- f() फ़ंक्शन परिभाषित करें। यह i, bs लेगा
- यदि i >= n, तो
- 1 लौटाएं
- ans := 0
- j के लिए 0 से n तक रेंज में, करें
- यदि matrix[i, j], 0 के समान है और (2^j AND bs, 0 के समान है), तो
- ans := ans + f(i + 1, bs OR 2^j)
- यदि matrix[i, j], 0 के समान है और (2^j AND bs, 0 के समान है), तो
- 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