পাইথনে ম্যাট্রিক্স থেকে স্বতন্ত্র দ্বীপের আকৃতি গণনা করা

ধরুন, একটি ২D বাইনারি ম্যাট্রিক্স দেওয়া আছে যেখানে ১ = স্থল, ০ = জল। একটি দ্বীপ হলো ১-দের একটি সংযুক্ত কম্পোনেন্ট। দুটি দ্বীপ স্বতন্ত্র (Distinct) হবে যদি তাদের আকৃতি (Shape) আলাদা হয়। আমাদের স্বতন্ত্র দ্বীপের সংখ্যা বের করতে হবে।

উদাহরণস্বরূপ, ইনপুট ম্যাট্রিক্স:

সমাধানের ধাপসমূহ

1. dfs(i, j, k, l) ফাংশন ডিফাইন করুন যা বর্তমান সেল (i,j) থেকে শুরু করে সমস্ত সংযুক্ত ১-কে ভিজিট করে এবং রিলেটিভ কোঅর্ডিনেট (i-k, j-l) একটি লিস্টে সংরক্ষণ করে।

2. প্রতিটি সেল (i,j) এর জন্য যদি মান ১ হয়, তবে dfs(i, j, i, j) কল করুন।

3. প্রাপ্ত আকৃতিকে টাপল (Tuple) বানিয়ে একটি সেটে shapes রাখুন।

4. যদি নতুন আকৃতি পাওয়া যায়, তবে কাউন্ট বাড়ান।

5. ফাইনাল কাউন্ট রিটার্ন করুন।

পাইথন কোড উদাহরণ

class Solution:
    def solve(self, mat):
        def dfs(i, j, k, l):
            mat[i][j] = 0
            shape.append((i - k, j - l))
            if i + 1 < len(mat) and mat[i + 1][j]:
                dfs(i + 1, j, k, l)
            if j + 1 < len(mat[0]) and mat[i][j + 1]:
                dfs(i, j + 1, k, l)
            if i - 1 >= 0 and mat[i - 1][j]:
                dfs(i - 1, j, k, l)
            if j - 1 >= 0 and mat[i][j - 1]:
                dfs(i, j - 1, k, l)
        cnt = 0
        shapes = set()
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                if mat[i][j]:
                    shape = []
                    dfs(i, j, i, j)
                    shape = tuple(shape)
                    if shape not in shapes:
                        cnt += 1
                    shapes.add(shape)
        return cnt

ob = Solution()
matrix = [
    [1, 0, 0, 0, 0],
    [1, 0, 1, 0, 1],
    [0, 1, 1, 0, 1],
    [0, 0, 1, 0, 0],
    [1, 0, 0, 0, 0],
    [1, 1, 0, 1, 1]
]
print(ob.solve(matrix))

ইনপুট

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

আউটপুট

4