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

मान लीजिए कि हमारे पास एक बाइनरी मैट्रिक्स है, हमें मैट्रिक्स में द्वीपों की संख्या ज्ञात करनी है। यहां 1 जमीन के लिए है और 0 पानी के लिए है, इसलिए एक द्वीप 1s का एक समूह है जो पड़ोसी हैं और जिनकी परिधि पानी से घिरी हुई है। यहां हम विचार कर रहे हैं कि पड़ोसी केवल क्षैतिज या लंबवत हो सकते हैं, विकर्ण नहीं।

तो, अगर इनपुट पसंद है

तो आउटपुट 4 होगा।

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

• एक फंक्शन एक्सप्लोर() परिभाषित करें। यह पंक्ति, कॉलम, मैट्रिक्स लेगा
• यदि पंक्ति और स्तंभ मैट्रिक्स या मैट्रिक्स की सीमा में नहीं हैं [पंक्ति, col] 0 है, तो
  • वापसी
• मैट्रिक्स[पंक्ति, कॉलम] :=0
• एक्सप्लोर करें(पंक्ति + 1, कॉलम, मैट्रिक्स)
• एक्सप्लोर करें(पंक्ति -1, कॉलम, मैट्रिक्स)
• एक्सप्लोर करें(पंक्ति, कॉलम + 1, मैट्रिक्स)
• एक्सप्लोर करें(पंक्ति, कॉलम -1, मैट्रिक्स)
• मुख्य विधि से, निम्न कार्य करें -
• यदि मैट्रिक्स शून्य है, तो
  • वापसी 0
• द्वीप :=0
• श्रेणी में पंक्ति के लिए 0 से लेकर मैट्रिक्स की पंक्ति गणना के लिए, करें
  • कॉलम के लिए 0 से लेकर मैट्रिक्स के कॉलम काउंट तक, करें
    • यदि मैट्रिक्स [पंक्ति, col] 1 के समान है, तो
      • द्वीप :=द्वीप + 1
      • एक्सप्लोर करें(पंक्ति, कॉलम, मैट्रिक्स)
• वापसी द्वीप

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

उदाहरण

class Solution:
   def explore(self, row, col, matrix):
   if (
         row < 0 or col < 0 or row > len(matrix) - 1 or col > len (matrix[0]) - 1 or          matrix[row][col] == 0):
         return
      matrix[row][col] = 0
      self.explore(row + 1, col, matrix)
      self.explore(row - 1, col, matrix)
      self.explore(row, col + 1, matrix)
      self.explore(row, col - 1, matrix)
      def solve(self, matrix):
         if not matrix:
            return 0
         islands = 0
         for row in range(len(matrix)):
            for col in range(len(matrix[0])):
               if matrix[row][col] == 1:
                  islands += 1
                  self.explore(row, col, matrix)
         return islands
ob = Solution() matrix = [
   [1, 0, 1, 0, 0],
   [0, 0, 1, 0, 0],
   [0, 1, 1, 0, 0],
   [0, 0, 0, 0, 0],
   [1, 1, 0, 1, 1],
   [1, 1, 1, 0, 1]
]
print(ob.solve(matrix))

इनपुट

[
   [1, 0, 1, 0, 0],
   [0, 0, 1, 0, 0],
   [0, 1, 1, 0, 0],
   [0, 0, 0, 0, 0],
   [1, 1, 0, 1, 1],
   [1, 1, 1, 0, 1]
]

आउटपुट

4