सभी 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