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

ধরুন আমাদের একটি বাইনারি ম্যাট্রিক্স আছে। যেখানে ১ হলো স্থল এবং ০ হলো জল। একটি দ্বীপ হলো ১-গুলোর একটি গোষ্ঠী যার পরিধি জল দিয়ে ঘেরা। আমাদের পুরোপুরি জল দিয়ে ঘেরা দ্বীপের সংখ্যা বের করতে হবে।

ইনপুট যদি নিচের মতো হয়:

তবে আউটপুট হবে ২, কারণ তিনটি দ্বীপ আছে কিন্তু দুটি পুরোপুরি ঘেরা।

সমাধানের ধাপগুলো:

একটি dfs() ফাংশন ডিফাইন করুন যা i, j গ্রহণ করে।
যদি i এবং j ম্যাট্রিক্সের বাইরে থাকে, তবে False রিটার্ন করুন।
যদি matrix[i][j] == 0 হয়, তবে True রিটার্ন করুন।
matrix[i][j] := 0 সেট করুন।
চার দিকেই ডিএফএস কল করুন: a = dfs(i+1, j), b = dfs(i-1, j), c = dfs(i, j+1), d = dfs(i, j-1)।
return a and b and c and d।
মেইন মেথড থেকে: R, C হিসেবে সারি ও কলামের সংখ্যা নিন, ans = 0।
সকল সেলের জন্য লুপ চালান, যদি matrix[i][j] == 1 হয় এবং dfs(i, j) true রিটার্ন করে তবে ans++।
শেষে ans রিটার্ন করুন।

উদাহরণ

class Solution:
    def solve(self, matrix):
        def dfs(i, j):
            if i < 0 or j < 0 or i >= R or j >= C:
                return False
            if matrix[i][j] == 0:
                return True
            matrix[i][j] = 0
            a = dfs(i + 1, j)
            b = dfs(i - 1, j)
            c = dfs(i, j + 1)
            d = dfs(i, j - 1)
            return a and b and c and d
        R, C = len(matrix), len(matrix[0])
        ans = 0
        for i in range(R):
            for j in range(C):
                if matrix[i][j] == 1:
                    if dfs(i, j):
                        ans += 1
        return ans

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

ইনপুট

matrix = [
    [1, 0, 0, 0, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 0, 0, 0],
    [0, 1, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
]