পাইথনে ম্যাট্রিক্স থেকে বাইরে যাওয়া না যাওয়া দ্বীপের সংখ্যা বের করার প্রোগ্রাম

ব্যাখ্যা: মাঝপথের ৪টি ভূমি সেল থেকে বাইরে যাওয়া যায় না। কোণাগুলোর ১গুলোর কাছ থেকে বাইরে যাওয়া যায়।

সমাধানের পদ্ধতি (BFS ফ্লড ফিল)

1. সীমানার সব ভূমি সেলগুলো একটি কিউ (q) তে সংগ্রহ করুন
2. সীমানার ভূমি সেলগুলো ০ করে দিন (ভিজিটেড চিহ্নিত)
3. BFS চালান: কিউ থেকে প্রতিটি সেলের জন্য ৪ দিক চেক করুন, যদি নতুন ভূমি সেল পাওয়া যায় তবে সেটাকে ০ করে কিউতে যোগ করুন
4. শেষে ম্যাট্রিক্সের সব সেলের যোগফল রিটার্ন করুন (যেটি অবশিষ্ট ভূমি সেলের সংখ্যা)

পাইথন কোড

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
    # BFS
    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))  # আউটপুট: 4

টেস্ট কেস

ইনপুট: [[0, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [0, 0, 0, 1]]
আউটপুট: 4