পাইথনে ২D ম্যাট্রিক্স থেকে ভিন্ন দ্বীপের সংখ্যা বের করুন

সমস্যা বিবরণ

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

উদাহরণস্বরূপ, নিচের গ্রিডে তিনটি দ্বীপ আছে।

সমাধানের ধাপসমূহ

1. numIslands(grid) মেথড:
   • যদি গ্রিড খালি হয়, রিটার্ন ০।
   • n = সারি, m = কলাম, ans = 0।
   • প্রতিটি সেল (i,j) için: যদি grid[i][j] == "1" হয়, ans++ এবং makeWater(i,j,n,m,grid) কল করুন।
   • ans রিটার্ন করুন।
2. makeWater(i,j,n,m,grid) মেথড:
   • বাউন্ডারি চেক: যদি বাইরে হয়, রিটার্ন।
   • যদি grid[i][j] == "0", রিটার্ন।
   • grid[i][j] = "0" (ভিজিটেড)।
   • চারদিকের সেলে রিকার্সিভলি কল করুন: (i+1,j), (i,j+1), (i-1,j), (i,j-1)।

পাইথন কোড উদাহরণ

class Solution:
    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
        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)

# টেস্ট
grid = [
    ["1","1","0","0","0"],
    ["1","1","0","0","0"],
    ["0","0","1","0","0"],
    ["0","0","0","1","1"]
]
sol = Solution()
print(sol.numIslands(grid))  # আউটপুট: 3

ইনপুট

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

আউটপুট

3