पायथन में एक-एक करके ब्लॉकों को ग्रिड में जोड़कर द्वीप गणना खोजने का कार्यक्रम

मान लीजिए हमारे पास पानी का एक अनंत ग्रिड है। हम उस ग्रिड में एक-एक करके भूमि के ब्लॉक जोड़ सकते हैं। हमारे पास निर्देशांकों की एक सूची है जिसे Land_requests कहा जाता है जहां प्रत्येक निर्देशांक [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) ]

• आईडीएक्स:=0

• एमपी:=एक नया नक्शा

• p :=एक नई सूची

• आकार :=एक नई सूची

• COMP:=0

• उत्तर :=एक नई सूची

• फ़ंक्शन खोज () को परिभाषित करें। यह आपको ले जाएगा

• यदि आप p[u] के समान हैं, तो

  • आप पर लौटें

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

• वापसी पी[यू]

• कनेक्ट() फ़ंक्शन को परिभाषित करें। यह आपको ले जाएगा, वी

• पु:=खोज(यू), पीवी:=खोज(वी)

• अगर पु, पीवी के समान है, तो

  • वापसी

• COMP :=COMP - 1

• अगर आकार [पु]> =आकार [पीवी], तो

  • पी[पीवी] :=पु

  • आकार [पु]:=आकार [पु] + आकार [पीवी]

• अन्यथा,

  • पी[पु] :=पीवी

  • आकार [पीवी]:=आकार [पीवी] + आकार [पु]

• मुख्य विधि से निम्न कार्य करें -

• Land_requests में प्रत्येक अनुरोध के लिए, करें

  • (i, j) :=अनुरोध

  • mp[i, j] :=idx

  • p के अंत में idx डालें

  • आकार के अंत में 1 डालें

  • आईडीएक्स:=आईडीएक्स + 1

  • COMP :=COMP + 1

  • d में प्रत्येक k के लिए, करें

    • नी:=मैं + के [1]

    • एनजे:=जे + के [0]

    • अगर (नी, एनजे) एमपी में है, तो

      • कनेक्ट (एमपी [(आई, जे)], एमपी [(नी, एनजे)])

  • उत्तर के अंत में 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]