पायथन का उपयोग करके बाइनरी ग्रिड की व्यवस्था करने के लिए न्यूनतम स्वैप खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक n x n बाइनरी मैट्रिक्स है। हम इस पर एक ऑपरेशन कर सकते हैं जैसे, एक चरण में हम दो आसन्न पंक्तियों का चयन करते हैं और उन्हें स्वैप करते हैं। हमें आवश्यक न्यूनतम स्वैप की संख्या गिननी होगी, ताकि मैट्रिक्स के प्रमुख विकर्ण के ऊपर सभी नोड्स 0 हों। यदि ऐसा कोई समाधान नहीं है, तो -1 लौटाएं।

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

0	1	0
0	1	1
1	0	0

तो आउटपुट 2 होगा क्योंकि -

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

n :=मैट्रिक्स की पंक्ति गणना
m :=आकार n की एक सरणी बनाएं और n से भरें
मैं के लिए 0 से n -1 की सीमा में, करो
- j के लिए n-1 से 0 की सीमा में, 1 से घटाएं, करें
  - यदि मैट्रिक्स [i, j] 1 के समान है, तो
    - मी[i] :=n-j-1
    - लूप से बाहर आएं
टी:=0, उत्तर:=0
मैं के लिए 0 से n -1 की सीमा में, करो
- टी:=टी + 1
- झंडा :=झूठा
- j के लिए I से n-1 की श्रेणी में, करें
  - अगर m[j]>=n-t, तो
    - उत्तर:=उत्तर + जे-आई
    - झंडा :=सच
    - लूप से बाहर आएं
- अगर झंडा झूठा है, तो
  - वापसी -1
- m[index i+1 to j] by m[index i to j-1]
  . को अपडेट करें
वापसी उत्तर

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

उदाहरण

def solve(matrix):
   n = len(matrix)
   m = [n] * n
   for i in range(n):
      for j in range(n-1,-1,-1):
         if matrix[i][j] == 1:
            m[i] = n-j-1
            break
   t,ans = 0,0
   for i in range(n):
      t += 1
      flag = False
      for j in range(i,n):
         if m[j] >= n-t:
            ans += j-i
            flag = True
            break
      if not flag: return -1
      m[i+1:j+1] = m[i:j]
   return ans
matrix = [[0,1,0],[0,1,1],[1,0,0]]
print(solve(matrix))

इनपुट

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