सभी 1s वाला अधिकतम आकार का वर्ग सबमैट्रिक्स

जब एक बाइनरी मैट्रिक्स दिया जाता है, तो हमारा कार्य एक ऐसा वर्ग मैट्रिक्स ढूंढना है जिसके सभी तत्व 1 हों।

इस समस्या के लिए, हम एक सहायक आकार मैट्रिक्स बनाएंगे, जिसका ऑर्डर दिए गए मैट्रिक्स जितना ही हो। यह आकार मैट्रिक्स प्रत्येक एंट्री Size[i, j] में, सभी 1s वाले वर्ग मैट्रिक्स के आकार को दर्शाने में मदद करेगा। उस आकार मैट्रिक्स से, हम सबसे बड़ी संख्या प्राप्त करके सबसे बड़े वर्ग मैट्रिक्स का आकार प्राप्त करेंगे।

इनपुट और आउटपुट

इनपुट: बाइनरी मैट्रिक्स
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

आउटपुट: सभी 1s वाला सबसे बड़ा सबमैट्रिक्स

एल्गोरिदम

subMatWithOne(given matrix)

इनपुट: मुख्य मैट्रिक्स
आउटपुट: सभी 1 वाला वर्ग मैट्रिक्स प्रदर्शित करें, जो सबसे बड़ा हो

शुरुआत
    subMat को दिए गए मैट्रिक्स के ऑर्डर जितना परिभाषित करें
    दिए गए मैट्रिक्स की पहली पंक्ति और पहले कॉलम को subMat में कॉपी करें
    सभी पंक्तियों i (1 से n) के लिए, करें
        सभी कॉलम j (1 से n) के लिए, करें
            यदि matrix[i, j] = 1, तो
                subMat[i, j] := 1 + subMat[i, j-1], subMat[i-1, j-1] का न्यूनतम
            अन्यथा
                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 < 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++)
        subMat[i][0] = matrix[i][0];
    
    for(int j = 0; j < COL; j++)
        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)
                subMat[i][j] = min(subMat[i][j-1], subMat[i-1][j], subMat[i-1][j-1]) + 1;
            else
                subMat[i][j] = 0;
        }
    }
    
    maxSize = subMat[0][0]; iMax = 0; jMax = 0;
    for(int i = 0; i < ROW; i++) {
        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--) {
        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