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

मान लीजिए हमारे पास पानी का एक अनंत ग्रिड है। हम उस ग्रिड में भूमि के ब्लॉक एक-एक करके जोड़ सकते हैं। हमारे पास निर्देशांकों की एक सूची है जिसे land_requests कहते हैं जहां प्रत्येक निर्देशांक [r, c] के रूप में है जहां r पंक्ति के लिए है और c स्तंभ के लिए। हमें एक सूची ज्ञात करनी है जहां प्रत्येक तत्व land_requests से भूमि के प्रत्येक ब्लॉक को जोड़ने के बाद मौजूद द्वीपों की संख्या दर्शाता है।

इसलिए, यदि इनपुट 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 := एक नई सूची

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

• comp := 0

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

• search() फ़ंक्शन परिभाषित करें। यह u लेगा

  • यदि u, p[u] के समान है, तो u लौटाएं

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

• p[u] लौटाएं

• connect() फ़ंक्शन परिभाषित करें। यह 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 में प्रत्येक request के लिए, करें

    • (i, j) := request

    • mp[i, j] := idx

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

    • 1 को size के अंत में डालें

    • idx := idx + 1

    • comp := comp + 1

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

      • ni := i + k[1]

      • nj := j + k[0]

      • यदि (ni, nj), mp में है, तो

        • connect(mp[(i, j)], mp[(ni, nj)])

    • comp को ans के अंत में डालें

  • 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]