পাইথনে দুটি মানচিত্রে ওভারল্যাপিং দ্বীপের সংখ্যা গণনা করার প্রোগ্রাম

ধরুন আমাদের দুটি বাইনারি ম্যাট্রিস mat1 এবং mat2 আছে। এখানে 1 ভূমিকে প্রতিনিধিত্ব করে এবং 0 জলকে প্রতিনিধিত্ব করে, যদি জল দ্বারা বেষ্টিত 1(ভূমি) গোষ্ঠী থাকে তবে তাকে দ্বীপ বলা হয়। আমাদের ঠিক একই স্থানাঙ্কে mat1 এবং mat2 উভয় ক্ষেত্রে বিদ্যমান দ্বীপের সংখ্যা খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুট mat1 =

এবং mat2 =

তাহলে আউটপুট হবে 2, কারণ ওভারল্যাপিং দ্বীপগুলি হল,

তাই দুটি ওভারল্যাপিং দ্বীপ আছে।

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

• r :=ম্যাট1 এর সারি গণনা
• c :=mat1 এর কলাম সংখ্যা
• last_row :=r - 1
• last_col :=c - 1
• একটি ফাংশন মার্ক () সংজ্ঞায়িত করুন। এর জন্য i, j
লাগবে
• mat1[i, j] :=0
• mat2[i, j] :=0
• যদি আমি শূন্য না হয় এবং (mat1[i - 1, j] বা mat2[i - 1, j] যেকোন একটি শূন্য না হয়), তাহলে
  • চিহ্ন(i - 1, j)
• যদি j অ শূন্য হয় এবং (mat1[i, j - 1] বা mat2[i, j - 1] যে কোনো একটি শূন্য হয় না, তাহলে
  • চিহ্ন(i, j - 1)
• যদি j
• চিহ্ন(i, j + 1)

উদাহরণ

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

def সমাধান(mat1, mat2):r =len(mat1) c =len(mat1[0]) last_row =r - 1 last_col =c - 1 def চিহ্ন(i, j):mat1[i][j ] =mat2[i][j] =0 যদি i এবং (mat1[i - 1][j] বা mat2[i - 1][j]):মার্ক(i - 1, j) যদি j এবং (mat1[ i][j - 1] বা mat2[i][j - 1]):মার্ক(i, j - 1) যদি j  
ইনপুট
 <প্রে>[[1, 0, 1],[1, 0, 0],[1, 0, 1]][[1, 0, 1],[1, 0, 0],[1, 0, 0]]

আউটপুট

2