मैट्रिक्स में पूरी तरह से घिरे हुए द्वीपों की संख्या गिनने का पायथन प्रोग्राम

मान लीजिए हमारे पास एक बाइनरी मैट्रिक्स है। जहां 1 भूमि दर्शाता है और 0 पानी दर्शाता है। जैसा कि हम जानते हैं एक द्वीप 1 का समूह है जो एक साथ जुड़े हुए हैं जिसकी परिधि पानी से घिरी हुई है। हमें पूरी तरह से घिरे हुए द्वीपों की संख्या ढूंढनी है।

उदाहरण के लिए, यदि इनपुट इस तरह है:

तो आउटपुट 2 होगा, क्योंकि तीन द्वीप हैं, लेकिन उनमें से दो पूरी तरह से घिरे हुए हैं।

इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:

• एक फ़ंक्शन dfs() परिभाषित करें। यह i, j लेगा
• यदि i और j मैट्रिक्स की सीमा में नहीं हैं, तो
  • False लौटाएं
• यदि matrix[i, j] 0 के समान है, तो
  • True लौटाएं
• matrix[i, j] := 0
• a := dfs(i + 1, j)
• b := dfs(i - 1, j)
• c := dfs(i, j + 1)
• d := dfs(i, j - 1)
• a and b and c and d लौटाएं
• मुख्य विधि से निम्न करें:
• R := मैट्रिक्स की पंक्ति संख्या, C := मैट्रिक्स की स्तंभ संख्या
• ans := 0
• i को 0 से R तक के लिए, करें
  • j को 0 से C तक के लिए, करें
    • यदि matrix[i, j] 1 के समान है, तो
      • यदि dfs(i, j) सत्य है, तो
        • ans := ans + 1
• ans लौटाएं

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

उदाहरण

class Solution:
    def solve(self, matrix):
        def dfs(i, j):
            if i < 0 or j < 0 or i >= R or j >= C:
                return False
            if matrix[i][j] == 0:
                return True
            matrix[i][j] = 0
            a = dfs(i + 1, j)
            b = dfs(i - 1, j)
            c = dfs(i, j + 1)
            d = dfs(i, j - 1)
            return a and b and c and d
        R, C = len(matrix), len(matrix[0])
        ans = 0
        for i in range(R):
            for j in range(C):
                if matrix[i][j] == 1:
                    if dfs(i, j):
                        ans += 1
        return ans

ob = Solution()
matrix = [
    [1, 0, 0, 0, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 0, 0, 0],
    [0, 1, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
]
print(ob.solve(matrix))

इनपुट

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

आउटपुट

2