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

ধরুন, আমাদের কাছে একটি অসীম জলের গ্রিড আছে। আমরা একে একে সেই গ্রিডেস্থল ব্লক যোগ করতে পারি। একটি কোঅর্ডিনেটের তালিকা দেওয়া আছে যার নাম land_requests, যেখানে প্রতিটি কোঅর্ডিনেট [r, c] আকারে (r = সারি, c = কলাম)। প্রতিটি ব্লক যোগ করার পর কতগুলো দ্বীপ আছে তা বের করতে হবে।

উদাহরণস্বরূপ, ইনপুট land_requests = [[1, 1], [2, 4], [1, 2], [1, 4], [1, 3]] হলে আউটপুট হবে [1, 2, 2, 2, 1]।

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

1. d := দিকের তালিকা: [(-1, 0), (0, 1), (1, 0), (0, -1)]

2. idx := 0, mp := নতুন ম্যাপ, p := নতুন লিস্ট, size := নতুন লিস্ট

3. comp := 0, ans := নতুন লিস্ট

4. search(u) ফাংশন ডিফাইন করুন:

   • যদি u == p[u] হয়, তবে u রিটার্ন করুন।

   • p[u] := search(p[u])

   • p[u] রিটার্ন করুন।

5. connect(u, v) ফাংশন ডিফাইন করুন:

   • pu := search(u), pv := search(v)

   • যদি pu == pv হয়, তবে রিটার্ন করুন।

   • comp := comp - 1

   • ইউনিয়ন বাই সাইজ (Union by Size) লজিক প্রয়োগ করুন।

6. প্রতিটি request ∈ land_requests এর জন্য:

   • (i, j) := request

   • mp[(i, j)] := idx; p.append(idx); size.append(1); idx += 1; comp += 1

   • প্রতিটি ডিরেকশন k ∈ d এর জন্য আশেপাশের সেল চেক করুন এবং যদি সেটি mp-তে থাকে তবে connect() কল করুন।

   • ans.append(comp)

7. ans রিটার্ন করুন।

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

d = [(-1, 0), (0, 1), (1, 0), (0, -1)]
class Solution:
    def search(self, u):
        if u == self.p[u]:
            return u
        self.p[u] = self.search(self.p[u])
        return self.p[u]
    def connect(self, u, v):
        pu = self.search(u)
        pv = self.search(v)
        if pu == pv:
            return
        self.comp -= 1
        if self.size[pu] >= self.size[pv]:
            self.p[pv] = pu
            self.size[pu] += self.size[pv]
        else:
            self.p[pu] = pv
            self.size[pv] += self.size[pu]
    def solve(self, land_requests):
        self.idx = 0
        self.mp = dict()
        self.p = []
        self.size = []
        self.comp = 0
        ans = []
        for request in land_requests:
            i, j = request
            self.mp[(i, j)] = self.idx
            self.p.append(self.idx)
            self.size.append(1)
            self.idx += 1
            self.comp += 1
            for k in d:
                ni = i + k[1]
                nj = j + k[0]
                if (ni, nj) in self.mp:
                    self.connect(self.mp[(i, j)], self.mp[(ni, nj)])
            ans.append(self.comp)
        return ans

ob = Solution()
land_requests = [[1, 1], [2, 4], [1, 2], [1, 4], [1, 3]]
print(ob.solve(land_requests))

ইনপুট

[[1, 1], [2, 4], [1, 2], [1, 4], [1, 3]]

আউটপুট

[1, 2, 2, 2, 1]