n×n बाइनरी मैट्रिक्स में एडजेसेंट रो स्वैप्स से मेजर डायगोनल के ऊपर सभी एलिमेंट्स 0 करने के लिए मिनिमम स्वैप्स ढूंढें।
एल्गोरिदम
- प्रत्येक रो के लिए राइटमोस्ट 1 की पोजीशन ढूंढें →
m[i] = n - j - 1(डायगोनल से दूरी)। - ग्रीडी: i=0 से n-1, ऐसी रो ढूंढें जिसका
m[j] >= n-i-1हो (यानी डायगोनल के ऊपर 1 न हो)। - उसे i-th पोजीशन पर लाने के लिए
j-iस्वैप्स करें (ऐरे शिफ्ट)। - नहीं मिली तो -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
# टेस्ट: [[0,1,0],[0,1,1],[1,0,0]] -> आउटपुट: 2
इनपुट/आउटपुट
इनपुट: [[0,1,0],[0,1,1],[1,0,0]]
आउटपुट: 2
