সব 1s সহ সর্বাধিক আকারের বর্গক্ষেত্র সাবম্যাট্রিক্স

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

এই সমস্যার জন্য, আমরা একটি সহায়ক আকারের ম্যাট্রিক্স তৈরি করব, যার ক্রম প্রদত্ত ম্যাট্রিক্সের মতোই। এই আকার ম্যাট্রিক্স প্রতিনিধিত্ব করতে সাহায্য করবে, প্রতিটি এন্ট্রি সাইজ [i, j], সমস্ত 1s সহ একটি বর্গ ম্যাট্রিক্সের আকার। সেই সাইজ ম্যাট্রিক্স থেকে, আমরা সবচেয়ে বড় বর্গ ম্যাট্রিক্সের সাইজ পেতে সর্বোচ্চ নম্বর পাব।

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

Input:
The binary matrix.
0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 1
0 0 0 0 0

Output:
The largest submatrix with all 1’s.

অ্যালগরিদম

subMatWithOne(given matrix)

ইনপুট - প্রধান ম্যাট্রিক্স।

আউটপুট - সমস্ত 1 দিয়ে বর্গ ম্যাট্রিক্স প্রদর্শন করুন, কোনটি সবচেয়ে বড়।

Begin
   define subMat whose order is same as given matrix
   copy first row and first column of given matrix to subMat

   for all row i (1 to n), do
      for all column j (1 to n), do
         if matrix[i, j] = 1, then
            subMat[i, j] := 1 + minimum of subMat[i, j-1]
            and subMat[i-1, j-1]
         else
            subMat[i, j] := 0
      done
   done

   maxSize := subMat[0, 0], iMax := 0 and jMax := 0
   for all row i and column j, do
      if maxSize < subMat[i, j], then
         maxSize := subMat[i, j]
         iMax := i, jMax := j
   done

   print sub matrix from row = iMax to (iMax - maxSize), and column jMax to (jMax - maxSize)
End

উদাহরণ

#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<b?a:b))?((a<c)?a:c):((b<c)?b:c);
}

void subMatWithOne() {
   int subMat[ROW][COL];
   int maxSize, iMax, jMax;

   for(int i = 0; i < ROW; i++)    //copy first row of matrix to sub matrix
      subMat[i][0] = matrix[i][0];

   for(int j = 0; j < COL; j++)    //copy first column of matrix to sub matrix
      subMat[0][j] = matrix[0][j];

   for(int i = 1; i < ROW; i++) {
      for(int j = 1; j < COL; j++) {
         if(matrix[i][j] == 1)    //find minimum of left, top and diagonal element + 1
            subMat[i][j] = min(subMat[i][j-1], subMat[i-1][j], subMat[i-1][j-1]) + 1;
         else
            subMat[i][j] = 0;    //if item is 0, put only 0
      }  
   }

   maxSize = subMat[0][0]; iMax = 0; jMax = 0;
   for(int i = 0; i < ROW; i++) {    //find the order of sub square matrix

      for(int j = 0; j < COL; j++) {
         if(maxSize < subMat[i][j]) {

            maxSize = subMat[i][j];
            iMax = i;
            jMax = j;
         }      
      }                
   }  
 
   cout << "Subsquare matrix: "<<endl;
   for(int i = iMax; i > iMax - maxSize; i--) {    //print the submatrix using max size
      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