পাইথনে অনুমোদিত কলামের অদলবদল সহ 1 এর বৃহত্তম আয়তক্ষেত্র খুঁজুন

ধরুন আমাদের একটি বাইনারি ম্যাট্রিক্স আছে, আমাদের সেই প্রদত্ত ম্যাট্রিক্সে সমস্ত 1 এর বৃহত্তম আয়তক্ষেত্র খুঁজে বের করতে হবে। সেই ম্যাট্রিক্সের যেকোন জোড়া কলাম অদলবদল বা বিনিময় করে আয়তক্ষেত্র তৈরি করা যেতে পারে।

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

তাহলে এই ক্ষেত্রে আউটপুট হবে 6। 3 এর সাথে কলাম 1 বিনিময় করে আয়তক্ষেত্র তৈরি করা যেতে পারে। বিনিময়ের পর ম্যাট্রিক্স হবে −

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

• সারি :=মাদুরের আকার

• col :=মাদুরের আকার[0]

• temp :=অর্ডারের একটি ম্যাট্রিক্স (সারি + 1) x (কল + 1), এবং 0 দিয়ে পূরণ করুন

• 0 থেকে col এর রেঞ্জের জন্য, করুন

  • temp[0, i] :=ম্যাট[0, i]

  • 1 থেকে সারি পর্যন্ত j এর জন্য, করুন

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

      • temp[j, i] :=0

    • অন্যথায়,

      • temp[j, i] :=temp[j - 1, i] + 1

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

  • cnt :=আকারের একটি অ্যারে (সারি + 1), এবং 0

    দিয়ে পূর্ণ

  • 0 থেকে col এর মধ্যে j এর জন্য, 1 দ্বারা বাড়ান, করুন

    • cnt[temp[i, j]] :=cnt[temp[i, j]] + 1

  • col_no :=0

  • j :=সারি

  • যখন j>=0, করবেন

    • যদি cnt[j]> 0 হয়, তাহলে

      • 0 থেকে cnt[j] রেঞ্জের k-এর জন্য, করুন

        • temp[i, col_no] :=j

        • col_no :=col_no + 1

    • j :=j - 1

• এলাকা_সর্বাধিক :=0

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

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

    • এলাকা_কারেন্ট :=(j + 1) * তাপমাত্রা[i, j]

    • যদি এলাকা_বর্তমান> এলাকা_সর্বাধিক, তাহলে

      • এলাকা_সর্বাধিক :=এলাকা_বর্তমান

• রিটার্ন এরিয়া_সর্বোচ্চ

উদাহরণ

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

def maxArea(mat):
   row = len(mat)
   col = len(mat[0])
   temp = [[0 for i in range(col + 1)] for i in range(row + 1)]
   for i in range(0, col):
      temp[0][i] = mat[0][i]
   for j in range(1, row):
      if ((mat[j][i] == 0)):
         temp[j][i] = 0
      else:
         temp[j][i] = temp[j - 1][i] + 1
   for i in range(0, row):
      cnt = [0 for i in range(row + 1)]
      for j in range(0, col, 1):
         cnt[temp[i][j]] += 1
      col_no = 0
      j = row
      while(j >= 0):
         if (cnt[j] > 0):
            for k in range(0, cnt[j]):
               temp[i][col_no] = j
               col_no += 1
         j -= 1
   area_maximum = 0
   for i in range(0, row):
      for j in range(0, col):
         area_current = (j + 1) * temp[i][j]
         if (area_current > area_maximum):
            area_maximum = area_current

   return area_maximum
mat = [
   [0, 0, 1, 1, 0],
   [0, 0, 1, 1, 1],
   [1, 0, 1, 1, 0]]
print("Area : ",maxArea(mat))

ইনপুট

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

আউটপুট

Area : 2