Chương trình tìm chu vi hình đảo trên ma trận nhị phân trong Python

Cho ma trận nhị phân (0 = ô trống, 1 = khối), tìm chu vi của hình dạng (không có lỗ bên trong).

Ví dụ: ma trận 5x5 như hình → kết quả 14.

Giải thuật (Duyệt từng ô - O(n*m))

1. Khởi tạo .
2. Duyệt từng ô :
   • Nếu :
     • Khởi tạo (4 cạnh).
     • Kiểm tra 4 hướng (trái, phải, trên, dưới): nếu ô láng giềng cũng là 1 → .
     • Cộng vào .
3. Trả về .

Ví dụ minh họa

class Solution:
    def solve(self, matrix):
        d = 0
        perimeter = 0
        height = len(matrix)
        length = len(matrix[0])
        for line in matrix:
            c = 0
            for val in line:
                if val == 1:
                    surround = 4
                    if c != length - 1 and matrix[d][c + 1] == 1:
                        surround -= 1
                    if c != 0 and matrix[d][c - 1] == 1:
                        surround -= 1
                    if d != height - 1 and matrix[d + 1][c] == 1:
                        surround -= 1
                    if d != 0 and matrix[d - 1][c] == 1:
                        surround -= 1
                    perimeter += surround
                c += 1
            d += 1
        return perimeter

ob = Solution()
matrix = [
    [0,0,0,0,0],
    [0,0,1,1,1],
    [0,0,1,1,0],
    [0,1,1,1,0],
    [0,0,0,0,0]
]
print(ob.solve(matrix))  # Output: 14

Đầu vào

matrix = [[0,0,0,0,0], [0,0,1,1,1], [0,0,1,1,0], [0,1,1,1,0], [0,0,0,0,0]]

Đầu ra

14