পাইথনে একটি জল সেল স্থল বদলে সর্ববৃহৎ দ্বীপ বের করা

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

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

1	0	1
0	0	0
1	1	0
1	1	1

আউটপুট হবে 7, কারণ একটি জল সেলকে স্থলে বদলে দুটি দ্বীপ সংযুক্ত করা যায়।

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

R, C := ম্যাট্রিক্সের সারি ও কলাম। mass := ডিকশনারি (দ্বীপ আইডি -> আকার)। id := 555 (শুরু)।
floodfill(r, c, id) ফাংশন ডিফাইন করুন:
- যদি সেল ভ্যালিড হয় এবং মান ১ হয়, তবে সেটিকে id দিয়ে মার্ক করুন, mass[id]++ করুন এবং ৪ দিকের প্রতিটি পাশে রিকার্সিভ কল দিন।
পুরো ম্যাট্রিক্স স্ক্যান করে প্রতিটি ১-কে নতুন আইডি দিয়ে ফ্লাডফিল চালান।
ans := সব দ্বীপের আকারের সর্বোচ্চ এবং ১।
প্রতিটি জল সেল (০) এর জন্য আশেপাশের ৪ দিক চেক করুন। যদি কোনো দ্বীপের আইডি পাওয়া যায়, তবে সেটি সেটে যোগ করুন। ans = max(ans, 1 + sum(mass[island])) আপডেট করুন।
ans রিটার্ন করুন।

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

class Solution:
    def solve(self, mat):
        R, C = len(mat), len(mat[0])
        mass = {}
        id = 555
        def floodfill(r, c, id):
            nonlocal R, C, mat, mass
            if 0 <= r < R and 0 <= c < C and mat[r][c] == 1:
                mat[r][c] = id
                mass[id] = mass.get(id, 0) + 1
                for r2, c2 in [(r+1, c), (r-1, c), (r, c+1), (r, c-1)]:
                    floodfill(r2, c2, id)
        for r in range(R):
            for c in range(C):
                if mat[r][c] == 1:
                    id += 1
                    mass[id] = 0
                    floodfill(r, c, id)
        ans = max([val for val in mass.values()] + [1])
        for r in range(R):
            for c in range(C):
                if mat[r][c] != 0:
                    continue
                island_set = set()
                for r2, c2 in [(r+1, c), (r-1, c), (r, c+1), (r, c-1)]:
                    if 0 <= r2 < R and 0 <= c2 < C and mat[r2][c2]:
                        island_set.add(mat[r2][c2])
                ans = max(ans, 1 + sum(mass[island] for island in island_set))
        return ans

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

ইনপুট

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