โปรแกรมหาจำนวนเกาะที่หลุดจากขอบเมทริกซ์ไม่ได้ใน Python

คำอธิบายปัญหา

กำหนดเมทริกซ์ไบนารี: 1=ที่ดิน, 0=น้ำ จากที่ดินเดินได้ 4 ทิศทาง หาจำนวนเซลล์ที่ดินที่ **ไม่สามารถเดินออกนอกเมทริกซ์ได้** (ถูกล้อมโดยน้ำ/ขอบ)

ตัวอย่าง

0 0 0 1
0 1 1 0
0 1 1 0
0 0 0 1

Output: 4 (บล็อก 2x2 กลาง อยู่ตำแหน่ง (1,1),(1,2),(2,1),(2,2) หลุดไม่ได้)

ขั้นตอนการแก้ปัญหา (BFS จากขอบ)

1. หาที่ดินบน **ขอบเมทริกซ์** ใส่คิว q และ mark = 0 (สามารถหลุดได้)
2. BFS จากคิว: ขยายไปที่ดินติดกัน ทำ mark = 0 ทั้งหมด
3. นับ 1 ที่เหลือในเมทริกซ์ = ที่ดินหลุดไม่ได้

การตนการทำงาน (Python)

def solve(matrix):
    q = [(i, j) for i in range(len(matrix))
                 for j in range(len(matrix[i]))
                 if matrix[i][j] and (i == 0 or i == len(matrix)-1 or j == 0 or j == len(matrix[i])-1)]
    idx = 0
    for x, y in q:
        matrix[x][y] = 0
    while idx < len(q):
        x, y = q[idx]
        for dx, dy in [(-1,0), (0,-1), (0,1), (1,0)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < len(matrix) and 0 <= ny < len(matrix[nx]) and matrix[nx][ny]:
                matrix[nx][ny] = 0
                q.append((nx, ny))
        idx += 1
    return sum(sum(row) for row in matrix)

matrix = [[0,0,0,1],[0,1,1,0],[0,1,1,0],[0,0,0,1]]
print(solve(matrix))  # Output: 4

อินพุต / เอาต์พุต

Input:  [[0,0,0,1],[0,1,1,0],[0,1,1,0],[0,0,0,1]]
Output: 4