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

ধরুন আমাদের কাছে পানির একটি অসীম গ্রিড আছে। আমরা এক এক করে সেই গ্রিডে জমির ব্লক যোগ করতে পারি। আমাদের কাছে ল্যান্ড_রিকোয়েস্ট নামক স্থানাঙ্কের একটি তালিকা রয়েছে যেখানে প্রতিটি স্থানাঙ্ক আকারে থাকে [r, c] যেখানে r হয় সারির জন্য এবং c হয় কলামের জন্য। আমাদের একটি তালিকা খুঁজে বের করতে হবে যেখানে প্রতিটি উপাদান ভূমি_অনুরোধ থেকে প্রতিটি ব্লক যোগ করার পরে বিদ্যমান দ্বীপের সংখ্যা উপস্থাপন করে।

সুতরাং, যদি ইনপুটটি হয় land_requests =[[1, 1],[2, 4],[1, 2],[1, 4],[1, 3]], তাহলে আউটপুট হবে [1, 2] , 2, 2, 1] হিসাবে

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• d :=দিকনির্দেশের একটি তালিকা যেমন [(−1, 0) ,(0, 1) ,(1, 0) ,(0, −1) ]

• idx :=0

• mp :=একটি নতুন মানচিত্র

• p :=একটি নতুন তালিকা

• আকার :=একটি নতুন তালিকা

• comp :=0

• উত্তর :=একটি নতুন তালিকা

• একটি ফাংশন অনুসন্ধান () সংজ্ঞায়িত করুন। এটি আপনাকে নিয়ে যাবে

• যদি u p[u] এর মত হয়, তাহলে

  • ফেরত দিন

  • p[u] :=অনুসন্ধান(p[u])

• ফিরে যান p[u]

• একটি ফাংশন সংযোগ () সংজ্ঞায়িত করুন। এটি আপনাকে, v

  নিয়ে যাবে

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

• যদি pu pv এর মত হয়, তাহলে

  • ফেরত

• comp :=comp − 1

• যদি size[pu]>=size[pv], তাহলে

  • p[pv] :=pu

  • size[pu] :=size[pu] + size[pv]

• অন্যথায়,

  • p[pu] :=pv

  • size[pv] :=size[pv] + size[pu]

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• land_requests-এ প্রতিটি অনুরোধের জন্য, করুন

  • (i, j) :=অনুরোধ

  • mp[i, j] :=idx

  • p

    এর শেষে idx ঢোকান

  • সাইজের শেষে 1 ঢোকান

  • idx :=idx + 1

  • comp :=comp + 1

  • প্রতিটি k-এর জন্য d, করুন

    • ni :=i + k[1]

    • nj :=j + k[0]

    • যদি (ni, nj) mp-এ থাকে, তাহলে

      • সংযোগ করুন(mp[(i, j)], mp[(ni, ​​nj)])

  • উত্তরের শেষে comp সন্নিবেশ করুন

• উত্তর ফেরত দিন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

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]