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

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

इसलिए, यदि इनपुट इस तरह है

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

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

• एक फ़ंक्शन explore() परिभाषित करें। यह row, col, matrix लेगा
• यदि row और col मैट्रिक्स की रेंज में नहीं हैं या matrix[row, col] 0 है, तो
  • वापस लौटें
• matrix[row, col] := 0
• explore(row + 1, col, matrix)
• explore(row - 1, col, matrix)
• explore(row, col + 1, matrix)
• explore(row, col - 1, matrix)
• मुख्य विधि से, निम्नलिखित करें −
• यदि matrix null है, तो
  • 0 वापस करें
• islands := 0
• row के लिए 0 से मैट्रिक्स की पंक्ति संख्या तक की रेंज में, करें
  • col के लिए 0 से मैट्रिक्स की कॉलम संख्या तक की रेंज में, करें
    • यदि matrix[row, col], 1 के समान है, तो
      • islands := islands + 1
      • explore(row, col, matrix)
• islands वापस करें

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

उदाहरण

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