โปรแกรมค้นหาเกาะที่ใหญ่ที่สุดหลังจากเปลี่ยนเซลล์น้ำหนึ่งเซลล์เป็นเซลล์บกใน Python

สมมติว่าเรามีเมทริกซ์ไบนารีโดยที่ 1 แทนดิน และ 0 แทนน้ำ และเกาะคือกลุ่มของ 1s ที่ล้อมรอบด้วยน้ำ เราต้องหาขนาดของเกาะที่ใหญ่ที่สุด เราได้รับอนุญาตให้เปลี่ยนเซลล์น้ำเป็นเซลล์พื้นดินได้ไม่เกินหนึ่งเซลล์

ดังนั้นหากอินพุตเป็นแบบ

จากนั้นผลลัพธ์จะเป็น 7 เนื่องจากเราสามารถเปลี่ยนเซลล์น้ำหนึ่งเซลล์ให้เป็นแผ่นดินเพื่อเชื่อมต่อสองเกาะ ดังนั้นเมทริกซ์สุดท้ายจึงเป็นแบบ −

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• R :=จำนวนแถวของเสื่อ C :=จำนวนคอลัมน์ของเสื่อ

• มวล :=แผนที่ใหม่

• id :=555

• กำหนดฟังก์ชั่น floodfill() นี่จะใช้เวลา r, c, id

• ถ้า r และ c อยู่ในช่วงของเมทริกซ์และ mat[r, c] คือ 1 แล้ว

  • mat[r, c] :=id

  • มวล[id] :=มวล[id] + 1

  • สำหรับแต่ละคู่ (r2, c2) ใน [(r + 1, c) ,(r − 1, c) ,(r, c + 1) ,(r, c − 1) ] ทำ

    • เติมน้ำท่วม(r2, c2, id)

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

• สำหรับ r ในช่วง 0 ถึง R ให้ทำ

  • สำหรับ c ในช่วง 0 ถึง C ให้ทำ

    • ถ้า mat[r, c] เหมือนกับ 1 แล้ว

      • id :=id + 1

      • มวล[id] :=0

      • เติมน้ำท่วม(r, c, id)

• ans :=สูงสุดของ (ค่าทั้งหมดของมวลและ 1)

• สำหรับ r ในช่วง 0 ถึง R − 1 ทำ

  • สำหรับ c ในช่วง 0 ถึง C − 1 ทำ

    • ถ้า mat[r, c] ไม่เหมือนกับ 0 แล้ว

      • ไปทำซ้ำต่อไป

    • island_set :=ชุดใหม่

    • สำหรับแต่ละคู่ (r2, c2) ใน [(r + 1, c) ,(r − 1, c) ,(r, c + 1) ,(r, c − 1) ] ทำ

      • ถ้า r2 และ c2 อยู่ในช่วงของ mat และ mat[r2, c2] คือ 1 แล้ว

        • เพิ่ม mat[r2, c2] ลงใน island_set

      • ans :=สูงสุดของ ans และ (1 + ผลรวมของมวลทั้งหมด[เกาะ] สำหรับแต่ละเกาะ inisland_set)

• กลับมาอีกครั้ง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

class Solution:
   def solve(self, mat):
      R, C = len(mat), len(mat[0])
      mass = {}
      id = 555
      def floodfill(r, c, id):
         nonlocal R, C, mat, mass
         if 0 <= r < R and 0 <= c < C and mat[r][c] == 1:
            mat[r][c] = id
            mass[id] += 1
            for r2, c2 in [(r + 1, c), (r − 1, c), (r, c + 1),
               (r, c − 1)]:
               floodfill(r2, c2, id)
                  for r in range(R):
      for c in range(C):
         if mat[r][c] == 1:
            id += 1
            mass[id] = 0
            floodfill(r, c, id)
      ans = max([val for val in mass.values()] + [1])
      for r in range(R):
         for c in range(C):
            if mat[r][c] != 0:
               continue
            island_set = set()
            for r2, c2 in [(r + 1, c), (r − 1, c), (r, c + 1),(r, c − 1)]:
               if 0 <= r2 < R and 0 <= c2 < C and mat[r2][c2]:
                  island_set.add(mat[r2][c2])
               ans = max(ans, 1 + sum([mass[island] for island in island_set]))
         return ans
ob = Solution()
matrix = [
   [1, 0, 1],
   [0, 0, 0],
   [1, 1, 0],
   [1, 1, 1]
]
print(ob.solve(matrix))

อินพุต

[
[1, 0, 1],
[0, 0, 0],
[1, 1, 0],
[1, 1, 1] ]

ผลลัพธ์

7