โปรแกรมค้นหาจำนวนเกาะโดยการเพิ่มบล็อกลงในตารางทีละรายการใน Python

สมมติว่าเรามีน้ำเป็นอนันต์หนึ่งตาราง เราสามารถเพิ่มบล็อกของที่ดินลงในตารางนั้นทีละรายการ เรามีรายการพิกัดที่เรียกว่า 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 :=รายการใหม่

• คอมพ์ :=0

• ans :=รายการใหม่

• กำหนดฟังก์ชัน search() นี้จะพาคุณ

• ถ้าคุณเหมือนกับ p[u] แล้ว

  • คืนคุณ

  • p[u] :=ค้นหา(p[u])

• กลับ p[u]

• กำหนดฟังก์ชั่น connect() นี้จะพาคุณ v

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

• ถ้า pu เหมือนกับ pv แล้ว

  • กลับ

• คอมพ์ :=คอมพ์ − 1

• ถ้า size[pu]>=size[pv] แล้ว

  • p[pv] :=ปู

  • ขนาด[pu] :=ขนาด[pu] + ขนาด[pv]

• มิฉะนั้น

  • p[pu] :=pv

  • ขนาด[pv] :=ขนาด[pv] + ขนาด[pu]

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• สำหรับแต่ละคำขอใน land_requests ให้ทำ

  • (i, j) :=ขอ

  • mp[i, j] :=idx

  • ใส่ idx ต่อท้าย p

  • แทรก 1 ที่ส่วนท้ายของขนาด

  • idx :=idx + 1

  • คอมพ์ :=คอมพ์ + 1

  • สำหรับแต่ละ k ใน d ทำ

    • พรรณี :=ผม + k[1]

    • nj :=j + k[0]

    • ถ้า (ni, nj) อยู่ใน mp แล้ว

      • เชื่อมต่อ(mp[(i, j)], mp[(ni, ​​nj)])

  • ใส่คอมพ์ที่ท้าย 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]