পাইথনে Number of Islands (দ্বীপের সংখ্যা গণনা)

মান করুন একটি গ্রিড আছে, সেখানে কিছু ০ এবং কিছু ১। আমাদের দ্বীপের সংখ্যা গণনা করতে হবে। দ্বীপ হচ্ছে যেটি জল দ্বারা ঘেরা এবং আড়াআড়ি ল্যান্ড (১) হরিজন্টালি বা ভার্টিক্যালি সংযুক্ত হয়ে তৈরি। আমরা ধরে নিতে পারি গ্রিডের চারপাশের সব এজ জল দ্বারা ঘেরা।

গ্রিড যদি নিচের মতো হয়:

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

সমাধানের ধাপগুলো (DFS ব্যবহার করে):

• দুটি মেথড থাকবে: numIslands() দ্বীপ গণনা করবে এবং makeWater()। makeWater() নিচের মতো:
  • যদি গ্রিডের সারি সংখ্যা ০ হয়, তবে ০ রিটার্ন করুন
  • n = সারি সংখ্যা, m := কলাম সংখ্যা, ans := 0
  • i ০ থেকে n-1 পর্যন্ত
    • j ০ থেকে m-1 পর্যন্ত
      • যদি grid[i][j] == "1", তবে ans += 1
      • makeWater(i, j, n, m, grid) কল করুন
  • makeWater() নিবে ইনডেক্স i, j, সারি ও কলাম সংখ্যা n, m, এবং গ্রিড
    • যদি i < 0 বা j < 0 বা i >= n বা j >= m, তবে রিটার্ন করুন
    • যদি grid[i][j] == "0", তবে রিটার্ন করুন, অন্যথায় grid[i][j] := "0" করুন
    • makeWater(i+1, j, n, m, grid) কল করুন
    • makeWater(i, j+1, n, m, grid) কল করুন
    • makeWater(i-1, j, n, m, grid) কল করুন
    • makeWater(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