C++-এ সমস্ত সমান উপাদান সহ সর্বাধিক বর্গাকার উপ-ম্যাট্রিক্স খোঁজা

এই সমস্যায়, আমাদের একটি 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 ম্যাট্রিক্সের যেকোন ঘরের প্রস্থ প্রণয়ন করি।

যদি উপাদানগুলির সমস্ত প্রতিবেশী একই হয় তবে আমরা দীর্ঘতম সাব-ম্যাট্রিক্সের মান বাড়াব। এই ক্ষেত্রে,

$DP[i][j]\:=\:মিনিট(DP[i-1][j] , DP[i][j-1], DP[i-1][j-1]) + 1$

যদি এটি না হয়,

DP[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