Python দিয়ে বাইনারি গ্রিড সাজাতে মিনিমাম সোয়াপ বের করার প্রোগ্রাম

মান লাগিয়ে, আমাদের একটি n x n বাইনারি ম্যাট্রিক্স আছে। আমরা এতে একটি অপারেশন করতে পারি: এক ধাপে দুটি আড়াঢাকের রো সিলেক্ট করে সোয়াপ করুন। আমাদের মিনিমাম কত সোয়াপ লাগবে যাতে ম্যাট্রিক্সের মেজর ডায়াগন্যালের উপরের সব নোড ০ হয়। যদি কোনো সমাধান না থাকে, তবে -1 রিটার্ন করুন।

যেমন, ইনপুট যদি এমন হয়:

0	1	0
0	1	1
1	0	0

তবে আউটপুট হবে 2 কারণ:

এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব:

n := ম্যাট্রিক্সের রো কাউন্ট
m := আকার n-এর একটি অ্যারে, n দিয়ে ভরা
i = 0 থেকে n - 1 পর্যন্ত:
- j = n-1 থেকে 0 পর্যন্ত কমতে কমতে:
  - যদি matrix[i][j] == 1 হয়, তবে m[i] := n-j-1 এবং লুপ থেকে বের হোন
t := 0, ans := 0
i = 0 থেকে n - 1 পর্যন্ত:
- t := t + 1
- flag := False
- j = i থেকে n - 1 পর্যন্ত:
  - যদি m[j] >= n-t হয়, তবে:
    - ans := ans + j-i
    - flag := True
    - লুপ থেকে বের হোন
- যদি flag false হয়, তবে -1 রিটার্ন করুন
- m[i+1:j+1] = m[i:j] দিয়ে আপডেট করুন
ans রিটার্ন করুন

বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন:

উদাহরণ

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]]