โปรแกรมนับจำนวนรูปทรงเกาะที่แตกต่างกันในเมทริกซ์ใน Python

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

ให้เมทริกซ์ไบนารี 2D 1=ที่ดิน 0=น้ำ เกาะคือกลุ่ม 1 ที่ติดกัน (4 ทิศทาง) สองเกาะถือว่ารูปทรงต่างกันถ้ารูปร่างไม่เหมือนกัน (ไม่พิจารณาตำแหน่ง) หาจำนวนรูปทรงเกาะที่แตกต่างกัน

ตัวอย่าง

เมทริกซ์ 6x5 → เอาต์พุต: 4 (มี 4 รูปทรงที่แตกต่างกัน)

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

ใช้ DFS + Normalization ของรูปทรง:

1. DFS จากทุกเซลล์ 1 ที่ยังไม่ได้เยี่ยม
2. บันทึกพิกัดสัมพัทธ์ (relative coordinates) เทียบกับจุดเริ่มต้น (i-k, j-l)
3. แปลง shape เป็น tuple แล้วเก็บใน set เพื่อเช็คความซ้ำ
4. นับจำนวน shape ที่ unique

โค้ด Python

class Solution:
    def solve(self, mat):
        def dfs(i, j, k, l):
            mat[i][j] = 0
            shape.append((i - k, j - l))
            if i + 1 < len(mat) and mat[i + 1][j]:
                dfs(i + 1, j, k, l)
            if j + 1 < len(mat[0]) and mat[i][j + 1]:
                dfs(i, j + 1, k, l)
            if i - 1 >= 0 and mat[i - 1][j]:
                dfs(i - 1, j, k, l)
            if j - 1 >= 0 and mat[i][j - 1]:
                dfs(i, j - 1, k, l)
        
        cnt = 0
        shapes = set()
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                if mat[i][j]:
                    shape = []
                    dfs(i, j, i, j)
                    shape = tuple(shape)
                    if shape not in shapes:
                        cnt += 1
                    shapes.add(shape)
        return cnt

ob = Solution()
matrix = [
    [1, 0, 0, 0, 0],
    [1, 0, 1, 0, 1],
    [0, 1, 1, 0, 1],
    [0, 0, 1, 0, 0],
    [1, 0, 0, 0, 0],
    [1, 1, 0, 1, 1]
]
print(ob.solve(matrix))

อินพุต

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

เอาต์พุต

4