โปรแกรมหาเส้นรอบรูปของเกาะในเมทริกซ์ไบนารีด้วย Python

สมมติว่าเรามีเมทริกซ์ไบนารีที่ 0 แทนช่องว่าง และ 1 แทนบล็อกที่สร้างรูปร่าง เราต้องหาเส้นรอบรูปของรูปร่างนั้น (รูปร่างไม่มีรูภายใน)

ตัวอย่างเมทริกซ์ 5x5:

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

ขั้นตอนการแก้ปัญหา (Count Exposed Edges)

1. วนลูปผ่านทุกเซลล์ในเมทริกซ์
2. หากเซลล์มีค่า 1:
   • เริ่มต้น surround = 4 (4 ด้าน)
   • ตรวจสอบ 4 ทิศทาง (บน, ล่าง, ซ้าย, ขวา) หากเพื่อนบ้านก็เป็น 1 ให้ surround -= 1
   • บวก surround เข้า perimeter
3. คืนค่า perimeter

ตัวอย่างโค้ด Python

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

อินพุต

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

เอาต์พุต

14