পাইথনে সম্পূর্ণরূপে জল দ্বারা বেষ্টিত সমস্ত দ্বীপ অপসারণের প্রোগ্রাম

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

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে

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

• সারি :=A

  এর সারি গণনা

• col :=A

  এর কলাম সংখ্যা

• B :=A আকারের একটি ম্যাট্রিক্স এবং 0

  দিয়ে পূরণ করুন

• দেখা হয়েছে :=একটি নতুন সেট

• আমি 0 থেকে সারি রেঞ্জের জন্য, করুন

  • j-এর জন্য 0 থেকে col, do

    • যদি i এবং j ম্যাট্রিক্সের পরিসরে না হয়, তাহলে

      • পরবর্তী পুনরাবৃত্তির জন্য যান

    • যদি (i, j) দেখা যায়, তাহলে

      • পরবর্তী পুনরাবৃত্তির জন্য যান

    • যদি A[i, j] 0 এর মত হয়, তাহলে

      • পরবর্তী পুনরাবৃত্তির জন্য যান

    • d :=একটি উপাদান (i, j)

      সহ একটি ডবল শেষ সারি

    • যখন d খালি নয়, করুন

      • (x, y) :=d-এর বাম উপাদান, এবং d

        থেকে মুছে দিন

      • B[x, y] :=1

      • প্রতিটি প্রতিবেশীর জন্য (x2, y2) (x, y), করুন

        • যদি (x2, y2) দেখা না হয়, তাহলে

          • d

            এর শেষে সন্নিবেশ করুন (x2, y2)

          • চিহ্ন (x2, y2) যেমন দেখা গেছে

• ফেরত B

উদাহরণ

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

সংগ্রহ থেকে আমদানি করুন dequeclass সমাধান:def solve(self, A):row =len(A) col =len(A[0]) B =[[0 for _ in range(col)] _ in range( সারি)] দেখা =সেট() def nei(i, j):যদি i + 1 =0 এবং A[i - 1][j]:ফলন (i - 1, j) যদি j - 1>=0 এবং ক 0, col - 1):continue if (i, j) in see:continue if A[i][j] ==0:continue d =deque([(i, j)]) যখন d:x, y =d.popleft() B[x][y] =1 এর জন্য x2, y2 in nei(x, y):যদি (x2, y2) দেখা না হয়:d.append((x2, y2)) see.add((x2, y2)) রিটার্ন বব =সমাধান()ম্যাট্রিক্স =[ [ [1, 0, 0, 0], [0, 1, 1, 0], [0, 1, 1, 0], [ 0, 1, 1, 0], [0, 0, 0, 1],]print(ob.solve(matrix))

ইনপুট

আউটপুট