সর্বোচ্চ আকারের সব ১ বিশিষ্ট বর্গাকার সাবম্যাট্রিক্স

যখন একটি বাইনারি ম্যাট্রিক্স দেওয়া থাকে, আমাদের কাজ হল এমন একটি বর্গাকার ম্যাট্রিক্স খুঁজে বের করা যার সকল উপাদান ১।

এই সমস্যার জন্য একটি অ্যাক্সিলিয়ারি সাইজ ম্যাট্রিক্স তৈরি করা হবে যেন এর আকার প্রদত্ত ম্যাট্রিক্সের সমান হয়। এই সাইজ ম্যাট্রিক্স প্রতিটি এন্ট্রি Size[i, j]-এ সব ১ বিশিষ্ট বর্গাকার ম্যাট্রিক্সের আকার নির্দেশ করবে। সেই সাইজ ম্যাট্রিক্স থেকে সর্বোচ্চ সংখ্যা বের করে সবচেয়ে বড় বর্গাকার ম্যাট্রিক্সের আকার পাওয়া যাবে।

ইনপুট এবং আউটপুট

ইনপুট: বাইনারি ম্যাট্রিক্স।
0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0

আউটপুট: সব ১ বিশিষ্ট সর্বোচ্চ সাবম্যাট্রিক্স।

অ্যালগরিদম

subMatWithOne(given matrix)

ইনপুট: মূল ম্যাট্রিক্স।
আউটপুট: সব ১ বিশিষ্ট বর্গাকার ম্যাট্রিক্স প্রদর্শন করা যেটি সবচেয়ে বড়।

শুরু
  প্রদত্ত ম্যাট্রিক্সের আকারের subMat সংজ্ঞায়িত করুন
  প্রদত্ত ম্যাট্রিক্সের প্রথম সারি এবং প্রথম কলাম subMat-এ কপি করুন
  সকল সারি i (১ থেকে n) জন্য, করুন
    সকল কলাম j (১ থেকে n) জন্য, করুন
      যদি matrix[i, j] = 1 হয়, তবে
        subMat[i, j] := 1 + subMat[i, j-1], subMat[i-1, j-1] এবং subMat[i-1, j]-এর মধ্যে ন্যূনতম
      অন্যথায়
        subMat[i, j] := 0
    শেষ
  শেষ
  maxSize := subMat[0, 0], iMax := 0 এবং jMax := 0
  সকল সারি i এবং কলাম j জন্য, করুন
    যদি maxSize < subMat[i, j] হয়, তবে
      maxSize := subMat[i, j]
      iMax := i, jMax := j
  শেষ
  সারি = iMax থেকে (iMax - maxSize) এবং কলাম jMax থেকে (jMax - maxSize) পর্যন্ত সাবম্যাট্রিক্স প্রিন্ট করুন
শেষ

উদাহরণ (C++)

#include <iostream>
#define ROW 6
#define COL 5
using namespace std;

int matrix[ROW][COL] = {
  {0, 1, 1, 0, 1},
  {1, 1, 0, 1, 0},
  {0, 1, 1, 1, 0},
  {1, 1, 1, 1, 0},
  {1, 1, 1, 1, 1},
  {0, 0, 0, 0, 0}
};

int min(int a, int b, int c) {
  return ((a iMax - maxSize; i--) {
    for(int j = jMax; j > jMax - maxSize; j--)
      cout << matrix[i][j] << " ";
    cout << endl;
  }
}

int main() {
  subMatWithOne();
}

আউটপুট

Subsquare matrix:
1 1 1
1 1 1
1 1 1