পাইথনে ম্যাট্রিক্সে সবচেয়ে বড় দ্বীপের এলাকা বের করার প্রোগ্রাম

মান লক্ষ্য করুন আমাদের কাছে একটি বাইনারি ম্যাট্রিক্স আছে। এখানে ১ উপস্থাপন করে ভূমি (land) এবং ০ উপস্থাপন করে জল (water)। একটি দ্বীপ (island) হল ১-গুলোর একটি গ্রুপ যারা পাশাপাশি (neighboring) আছে এবং যাদের পরিসীমা জল দিয়ে ঘেরা। আমরা ধরে নিতে পারি ম্যাট্রিক্সের প্রান্তগুলো জল দিয়ে ঘেরা। আমাদের কাজ হল ম্যাট্রিক্সে সবচেয়ে বড় দ্বীপের এলাকা বের করা।

উদাহরণস্বরূপ, যদি ইনপুট হয়:

তবে আউটপুট হবে 6।

• একটি dfs() ফাংশন ডিফাইন করুন যা matrix, r, c নেবে।
  • total := total + 1
  • matrix[r][c] := 0 (ভিজিটেড মার্ক)
  • যদি r-1 >= 0 এবং matrix[r-1][c] == 1 হয়, তবে dfs(matrix, r-1, c)
  • যদি c-1 >= 0 এবং matrix[r][c-1] == 1 হয়, তবে dfs(matrix, r, c-1)
  • যদি r+1 < r_len এবং matrix[r+1][c] == 1 হয়, তবে dfs(matrix, r+1, c)
  • যদি c+1 < c_len এবং matrix[r][c+1] == 1 হয়, তবে dfs(matrix, r, c+1)
• মূল মেথড থেকে:
  • r_len := len(matrix), c_len := len(matrix[0])
  • max_island := 0
  • r কে ০ থেকে r_len-1 পর্যন্ত লুপ চালান:
    • c কে ০ থেকে c_len-1 পর্যন্ত লুপ চালান:
      • যদি matrix[r][c] == 1 হয়, তবে:
        • total := 0
        • dfs(matrix, r, c)
        • max_island := max(max_island, total)
  • max_island রিটার্ন করুন।
  উদাহরণ কোড

  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