পাইথনে বাইনারি ম্যাট্রিক্স-এ সব ১ থাকা বর্গাকার সাবম্যাট্রিক্সের সংখ্যা বের করার প্রোগ্রাম

ব্যাখ্যা: একটা ২×২ বর্গ এবং চারটা ১×১ বর্গ = মোট ৫টি।

সমাধানের পদ্ধতি (ডাইনামিক প্রোগ্রামিং)

1. যদি ম্যাট্রিক্স খালি হলে ০ রিটার্ন করুন
2. c = 0 (কাউন্টার)
3. প্রতিটি সেল (i, j) এর জন্য:
   • যদি mat[i][j] == 1:
     • যদি i == 0 or j == 0: c += 1 (প্রথম সারি/কলামে ১×১ বর্গ)
     • অন্যথায়:
       • temp = min(mat[i-1][j-1], mat[i][j-1], mat[i-1][j]) + mat[i][j]
       • c += temp
       • mat[i][j] = temp (ইন-প্লেস আপডেট)
4. c রিটার্ন করুন

পাইথন কোড

def solve(mat):
    if mat == []:
        return 0
    c = 0
    for i in range(len(mat)):
        for j in range(len(mat[0])):
            if mat[i][j] == 1:
                if i == 0 or j == 0:
                    c += 1
                else:
                    temp = (min(mat[i - 1][j - 1], mat[i][j - 1], mat[i - 1][j]) + mat[i][j])
                    c += temp
                    mat[i][j] = temp
    return c

matrix = [
    [0, 1, 1],
    [0, 1, 1]
]
print(solve(matrix))  # আউটপুট: 5

টেস্ট কেস

ইনপুট: [[0, 1, 1], [0, 1, 1]]
আউটপুট: 5