Chương trình đếm số hình dạng đảo khác nhau từ ma trận cho trước trong Python

Cho ma trận nhị phân 2D, đếm số đảo có hình dạng khác nhau. 1 là đất, 0 là nước. Hai đảo được coi là khác nhau nếu hình dạng của chúng khác nhau (không tính vị trí).

Ví dụ ma trận 6x5 cho kết quả 4 hình dạng đảo khác nhau.

Giải pháp

Sử dụng DFS để ghi nhận hình dạng tương đối của từng đảo:

• Duyệt ma trận, khi gặp 1 chưa thăm, chạy DFS từ ô đó
• Trong DFS: đánh dấu đã thăm, lưu tọa độ tương đối so với ô bắt đầu (i-k, j-l)
• Chuyển danh sách tọa độ tương đối thành tuple, thêm vào set shapes
• Kết quả là kích thước của set shapes

Ví dụ minh họa

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))

Đầu vào

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

Đầu ra

4