Python प्रोग्राम - उन द्वीपों की संख्या खोजें जहां से बाहर नहीं जा सकते

एक बाइनरी मैट्रिक्स दिया गया है जहां 1 जमीन दर्शाता है और 0 पानी। किसी भी जमीन से हम ऊपर, नीचे, बाएं या दाएं जा सकते हैं (तिरछे नहीं) दूसरी जमीन सेल पर या मैट्रिक्स से बाहर। हमें उन जमीन सेल की संख्या खोजनी है जहां से हम मैट्रिक्स से बाहर नहीं जा सकते।

उदाहरण

इनपुट मैट्रिक्स:

आउटपुट: 4

व्याख्या: बीच में 4 जमीन वर्ग हैं जहां से हम मैट्रिक्स से बाहर नहीं चल सकते।

एल्गोरिदम (BFS दृष्टिकोण)

1. बॉर्डर पर मौजूद सभी जमीन सेल (1) को क्यू q में जोड़ें
2. इन बॉर्डर सेल को 0 पर सेट करें (देखा गया मार्क करें)
3. BFS चलाएं: क्यू से प्रत्येक सेल के लिए, उसके 4 पड़ोसियों (ऊपर, नीचे, बाएं, दाएं) की जांच करें
4. यदि पड़ोसी वैध है और जमीन (1) है, तो उसे 0 पर सेट करें और क्यू में जोड़ें
5. अंत में, मैट्रिक्स में शेष सभी 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
    # बॉर्डर सेल को 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

इनपुट/आउटपुट

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