पायथन में एक मैट्रिक्स में सबसे बड़े द्वीप का क्षेत्रफल खोजने का कार्यक्रम

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

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

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

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

• एक फ़ंक्शन को परिभाषित करें dfs() । यह मैट्रिक्स लेगा, r, c
• कुल :=कुल + 1
• मैट्रिक्स[आर, सी] :=0
• यदि r - 1>=0 और मैट्रिक्स [r - 1, c] 1 के समान है, तो
  • dfs(मैट्रिक्स, r-1, c)
• यदि c - 1>=0 और मैट्रिक्स [r, c - 1] 1 के समान है, तो
  • dfs(मैट्रिक्स, r, c - 1)
• यदि r + 1
• dfs(मैट्रिक्स, r + 1, c)

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

उदाहरण

class Solution:
   def solve(self, matrix):
      self.r_len = len(matrix)
      self.c_len = len(matrix[0])
      max_island = 0
      for r in range(self.r_len):
         for c in range(self.c_len):
            if matrix[r][c] == 1:
               self.total = 0
               self.dfs(matrix, r, c)
               max_island = max(max_island, self.total)
      return max_island
   def dfs(self, matrix, r, c):
      self.total += 1
      matrix[r][c] = 0
      if r - 1 >= 0 and matrix[r - 1][c] == 1:
         self.dfs(matrix, r - 1, c)
      if c - 1 >= 0 and matrix[r][c - 1] == 1:
         self.dfs(matrix, r, c - 1)
      if r + 1 < self.r_len and matrix[r + 1][c] == 1:
         self.dfs(matrix, r + 1, c)
      if c + 1 < self.c_len and matrix[r][c + 1] == 1:
         self.dfs(matrix, r, c + 1)
ob = Solution()
matrix = [ [0, 0, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 0, 0], [0, 0, 1, 1, 0, 0, 0], [0, 0, 0, 0, 0, 1, 1], [0, 0, 0, 0, 0, 1, 0] ]
print(ob.solve(matrix))

इनपुट

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

आउटपुट

6