পাইথনে একটি 2D ম্যাট্রিক্সে স্বতন্ত্র দ্বীপের সংখ্যা খুঁজুন

ধরুন আমাদের একটি বাইনারি ম্যাট্রিক্স আছে। এতে আমাদের দ্বীপের সংখ্যা গুনতে হবে। একটি দ্বীপ হল এমন জায়গা যা জল দ্বারা বেষ্টিত এবং অনুভূমিকভাবে বা উল্লম্বভাবে সংলগ্ন জমিগুলিকে সংযুক্ত করে গঠিত হয়। আমরা অনুমান করতে পারি যে গ্রিডের চারটি প্রান্তই জল দ্বারা বেষ্টিত৷

ধরুন গ্রিড −

তিনটি দ্বীপ আছে৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• দুটি পদ্ধতি থাকবে, একটি ব্যবহার করা হবে numIslands() এবং makeWater() নামক দ্বীপের সংখ্যা গণনা করতে। makeWater() হবে −

  এর মত

• যদি গ্রিডে সারির সংখ্যা 0 হয়, তাহলে 0

  ফেরত দিন

• n =সারি গণনা এবং m :=কলাম গণনা, এবং উত্তর :=0

• 0 থেকে n – 1

  রেঞ্জের i জন্য

  • j এর জন্য 0 থেকে m

    পরিসরে

    • যদি গ্রিড[i, j] =1 হয়, তাহলে ans :=ans + 1

    • makeWater(i, j, n, m, grid)

• makeWater() সূচক i, j, রো এবং col কাউন্ট n এবং m, এবং গ্রিড নিবে

• যদি i <0 বা j <0 বা i>=n বা j>=m, তাহলে এই পদ্ধতি থেকে ফিরে আসুন

• যদি গ্রিড[i, j] =0 হয়, তাহলে ফিরে যান অন্যথায় গ্রিড করুন [i, j] :=0

• মেকওয়াটারকে কল করুন(i + 1, j, n, m, grid)

• মেকওয়াটারকে কল করুন(i, j + 1, n, m, grid)

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

class Solution(object):
   def numIslands(self, grid):
      """
      :type grid: List[List[str]]
      :rtype: int
      """
      if len(grid) == 0:
         return 0
      n= len(grid)
      m = len(grid[0])
      ans = 0
      for i in range(n):
         for j in range(m):
            if grid[i][j] == "1":
               ans+=1
            self.make_water(i,j,n,m,grid)
         return ans
   def make_water(self,i,j,n,m,grid):
      if i<0 or j<0 or i>=n or j>=m:
         return
      if grid[i][j] == "0":
         return
      else:
         grid[i][j]="0"
      self.make_water(i+1,j,n,m,grid)
      self.make_water(i,j+1,n,m,grid)
      self.make_water(i-1,j,n,m,grid)
      self.make_water(i,j-1,n,m,grid)

ইনপুট

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

আউটপুট

3