পাইথনে দুটি ম্যাপে ওভারল্যাপিং দ্বীপের সংখ্যা গণনা করার প্রোগ্রাম

মান লওয়া যাক দুটি বাইনারি ম্যাট্রিক্স mat1 এবং mat2 আছে। এখানে ১ মানে ল্যান্ড (স্থল) এবং ০ মানে ওয়াটার (পানি)। যদি ১ (ল্যান্ড) এর একটি গ্রুপ পানির দ্বারা ঘেরা থাকে, তাকে দ্বীপ (island) বলা হয়। আমাদের বের করতে হবে দুটি ম্যাট্রিক্সে একই কোঅর্ডিনেটে কতগুলো দ্বীপ وجود করে।

উদাহরণ

mat1:

mat2:

আউটপুট: 2

কারণ ওভারল্যাপিং দ্বীপগুলো হলো (হাইলাইট করা部分):

এখানে দুটি ওভারল্যাপিং দ্বীপ পাওয়া গেলো।

এলগরিদম

1. r, c = ম্যাট্রিক্সের সারি ও কলাম সংখ্যা
2. mark(i, j) ফাংশন ডিফাইন করুন যা (i, j) পজিশন থেকে শুরু করে দুটি ম্যাট্রিক্সেই কানেক্টেড ল্যান্ডকে ০ করে দেয় (ভিজিটেড মارک)। এটি ৪ দিক (আপ, ডাউন, লেফ্ট, রাইট) রিকার্শিভলি চেক করে।
3. প্রথমে: যেখানে mat1[i][j] != mat2[i][j] সেখানে mark(i, j) কল করে নন-ওভারল্যাপিং ল্যান্ড মুছে ফেলুন।
4. তারপর: বাকি থাকা ল্যান্ড (mat1[i][j] == 1) গুলো গণনা করুন এবং প্রতিটির জন্য mark(i, j) কল করুন।
5. গণনা করা সংখ্যাটিই ওভারল্যাপিং দ্বীপের সংখ্যা।

পাইথন ইমপ্লিমেন্টেশন

def solve(mat1, mat2):
    r = len(mat1)
    c = len(mat1[0])
    last_row = r - 1
    last_col = c - 1
    
    def mark(i, j):
        mat1[i][j] = mat2[i][j] = 0
        if i and (mat1[i-1][j] or mat2[i-1][j]):
            mark(i-1, j)
        if j and (mat1[i][j-1] or mat2[i][j-1]):
            mark(i, j-1)
        if j < last_col and (mat1[i][j+1] or mat2[i][j+1]):
            mark(i, j+1)
        if i < last_row and (mat1[i+1][j] or mat2[i+1][j]):
            mark(i+1, j)
    
    # নন-ওভারল্যাপিং ল্যান্ড মুছে ফেলা
    for i in range(r):
        for j in range(c):
            if mat1[i][j] != mat2[i][j]:
                mark(i, j)
    
    # ওভারল্যাপিং দ্বীপ গণনা
    islands = 0
    for i in range(r):
        for j in range(c):
            if mat1[i][j]:
                islands += 1
                mark(i, j)
    return islands

mat1 = [[1, 0, 1], [1, 0, 0], [1, 0, 1]]
mat2 = [[1, 0, 1], [1, 0, 0], [1, 0, 0]]
print(solve(mat1, mat2))  # Output: 2

ইনপুট

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

আউটপুট

2

ব্যাখ্যা

• mark() ফাংশনটি DFS (Depth-First Search) ব্যবহার করে কানেক্টেড কম্পোনেন্ট মুছে ফেলে।
• প্রথম পাসে: যেখানে দুটি ম্যাট্রিক্স ভিন্ন (একটিতে ল্যান্ড, অন্যটিতে ওয়াটার), সেখানে থেকে শুরু করে উভয় ম্যাট্রিক্সেই কানেক্টেড ল্যান্ড মুছে ফেলা হয়। এতে শুধু ওভারল্যাপিং ল্যান্ড বাকি থাকে।
• দ্বিতীয় পাসে: বাকি থাকা ল্যান্ডগুলো গণনা করা হয় এবং প্রতিটি দ্বীপের জন্য mark() কল করে ভিজিটেড মارک করা হয়।
• সময় জটিলতা: O(r × c), স্পেস: O(r × c) (রিকার্শন স্ট্যাক)।