सी ++ में सभी समान तत्वों के साथ अधिकतम वर्ग उप-मैट्रिक्स ढूँढना

इस समस्या में, हमें एक N*N मैट्रिक्स मैट [] दिया जाता है। हमारा काम है सभी समान तत्वों के साथ अधिकतम वर्ग उप-मैट्रिक्स ढूँढना ।

इस समस्या में, हमें दिए गए मैट्रिक्स से एक उप-मैट्रिक्स का अधिकतम आकार खोजने की आवश्यकता है, जिसके सभी तत्व समान हैं।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

Input: mat[][] = {{1, 2, 1}, {1, 2, 2}, {2, 2, 2}}
Output: 2

स्पष्टीकरण -

matrix a₁₁, a₁₂, a₂₁, a₂₂ is of size 2X2 and forms a sub-matrix with all equal elements.

समाधान दृष्टिकोण

समस्या का एक सरल समाधान मैट्रिक्स के सभी तत्वों का पता लगाना है और फिर उन सभी उप-मैट्रिसेस की जांच करना है जिनमें समान तत्व हैं। एल्गोरिथम की समय जटिलता O(n³ .) है ) और प्रत्येक उप-मैट्रिक्स O(n² . की समय जटिलता के साथ बनाया गया है )।

एक वैकल्पिक तरीका समस्या को हल करने के लिए गतिशील प्रोग्रामिंग का उपयोग किया जा रहा है जहां हम सब-मैट्रिक्स के सबसे बड़े आकार को सभी तत्वों के साथ स्थिति तक स्टोर करेंगे। इसके लिए हम पड़ोसी तत्वों पर विचार करेंगे और फिर दी गई शर्त को पूरा करने वाले सबसे लंबे मैट्रिक्स पर विचार करेंगे। आइए डीपी मैट्रिक्स के किसी भी सेल की चौड़ाई तैयार करें।

यदि तत्वों के सभी पड़ोसी समान हैं, तो हम सबसे लंबे उप-मैट्रिक्स के मूल्यों में वृद्धि करेंगे। इस मामले में,

$DP[i][j]\:=\:min(DP[i-1][j] , DP[i][j-1], DP[i-1][j-1]) + 1$

अगर ऐसा नहीं है,

डीपी[i][j] =1

उदाहरण

हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम

#include<bits/stdc++.h>
#define n 4
#define m 4
using namespace std;
int findmaxSqMatSize(int mat[][m]){
   int DP[n][m];
   memset(DP, sizeof(DP), 0);
   int maxSqMatSize = 0;
   for (int i = 0 ; i < n ; i++){
      for (int j = 0 ; j < m ; j++){
         if (i == 0 || j == 0)
            DP[i][j] = 1;
         else{
            if (mat[i][j] == mat[i-1][j] && mat[i][j] == mat[i][j-1] && mat[i][j] == mat[i-1][j-1] )
               DP[i][j] = min(min(DP[i-1][j], DP[i][j-1]), DP[i-1][j-1] ) + 1;
            else DP[i][j] = 1;
         }
         maxSqMatSize = max(maxSqMatSize, DP[i][j]);
      }
   }
   return maxSqMatSize;
}
int main(){
   int mat[n][m] = { {2, 1, 4, 3},
   {5, 1, 1, 7},
   {1, 1, 1, 4},
   {9, 4, 6, 0}};
   cout<<"The maximum square sub-matrix with all equal elements is "<<findmaxSqMatSize(mat);
   return 0;
}

आउटपुट

The maximum square sub-matrix with all equal elements is 2