এই সমস্যাতে, আমাদের একটি N*N ম্যাট্রিক্স mat[] দেওয়া আছে। আমাদের কাজ হল সর্বোচ্চ বর্গাকার সাব-ম্যাট্রিক্স বের করা যেটির সব এলিমেন্ট সমান।
এই সমস্যাতে, আমাদের দেয়া ম্যাট্রিক্স থেকে সর্বোচ্চ সাইজের সাব-ম্যাট্রিক্স বের করতে হবে যেটির সব এলিমেন্ট একই।
উদাহরণ দেখি:
ইনপুট: mat[][] = {{1, 2, 1}, {1, 2, 2}, {2, 2, 2}} আউটপুট: 2
ব্যাখ্যা -
ম্যাট্রিক্স a11, a12, a21, a22 ২x২ সাইজের একটি সাব-ম্যাট্রিক্স যেটির সব এলিমেন্ট সমান।
সমাধানের পদ্ধতি
একটি সহজ পদ্ধতি হল ম্যাট্রিক্সের সব এলিমেন্ট ট্রাভার্স করে সব সাব-ম্যাট্রিক্স চেক করা যেগুলোর এলিমেন্ট একই। অ্যালগরিদমের টাইম কমপ্লেক্সিটি O(n3) এবং প্রতিটি সাব-ম্যাট্রিক্স তৈরি হয় O(n2) টাইমে।
বিকল্প পদ্ধতি হল ডাইনামিক প্রোগ্রামিং ব্যবহার করা যেখানে আমরা প্রতিটি পজিশন পর্যন্ত সবচেয়ে বড় সাব-ম্যাট্রিক্সের সাইজ স্টোর করব যেটির সব এলিমেন্ট একই। এর জন্য আমরা প্রতিবেশী এলিমেন্টগুলো বিবেচনা করব এবং দীর্ঘতম ম্যাট্রিক্স বিবেচনা করব যেটি কন্ডিশন সন্তুষ্ট করে। DP ম্যাট্রিক্সের যেকোনো সেলের প্রস্থ ফর্মুলেট করি।
যদি সব প্রতিবেশী এলিমেন্ট একই হয়, তবে লংগেস্ট সাব-ম্যাট্রিক্সের ভ্যালু বাড়াব। এই ক্ষেত্রে,
$DP[i][j]\: =\: min(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
