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

คำอธิบายโจทย์

ให้เมทริกซ์ไบนารี 1 = ที่ดิน, 0 = น้ำ เกาะคือกลุ่ม 1 ที่ติดกัน (4 ทิศทาง) ถูมน้ำหรือขอบล้อมรอบ สามารถเปลี่ยนเซลล์น้ำสูงสุด 1 เซลล์เป็นที่ดิน หาขนาดเกาะใหญ่สุดที่เป็นไปได้

ตัวอย่าง

เมทริกซ์:

วิธีแก้ปัญหา

1. Flood fill ทุกเกาะ ตั้ง ID ให้แต่ละเกาะ และบันทึกขนาด (mass) ของแต่ละ ID
2. สำหรับแต่ละเซลล์น้ำ (0) ดูเพื่อนบ้าน 4 ทิศทาง รวบรวม ID ของเกาะที่ติดกัน (ไม่ซ้ำกัน)
3. ขนาดเกาะใหม่ = 1 (เซลล์ที่เปลี่ยน) + ผลรวม mass ของเกาะที่ติดกัน
4. หาค่าสูงสุด รวมถึงกรณีไม่เปลี่ยนเซลล์ใดๆ (เกาะใหญ่สุดเดิม)

โค้ด Python

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] = mass.get(id, 0) + 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