পাইথনে দ্বীপের সংখ্যা

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

ধরুন গ্রিড −

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

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

• দুটি পদ্ধতি থাকবে, একটি ব্যবহার করা হবে numIslands() এবং makeWater() নামক দ্বীপের সংখ্যা গণনা করতে। makeWater() হবে −
এর মত
• যদি গ্রিডে সারির সংখ্যা 0 হয়, তাহলে 0 ফেরত দিন
• n =সারি গণনা এবং m :=কলাম গণনা, এবং উত্তর :=0
• আমি 0 থেকে n – 1
  পরিসরে 0 থেকে m
  পরিসরে j-এর জন্য
  • যদি গ্রিড[i, j] =1, তাহলে ans :=ans + 1
  • makeWater(i, j, n, m, grid)
• মেকওয়াটার() সূচক 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):
      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)
ob1 = Solution()
print(ob1.numIslands([["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],
["0","0","0","1","1"]]))

ইনপুট

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

আউটপুট

3