এই সমস্যায়, আমাদের nXm আকারের একটি বাইনারি ম্যাট্রিক্স বিন [][][] দেওয়া হয়েছে। আমাদের কাজ হল সমস্ত q প্রশ্নের সমাধান করা। কোয়েরির জন্য(x, y), আমাদেরকে x*x আকারের সাবম্যাট্রিক্সের সংখ্যা খুঁজে বের করতে হবে যাতে অ্যারের y (বাইনারী সংখ্যা) এর সমস্ত উপাদান।
সমস্যা বর্ণনা
এখানে, আমাদের একটি প্রদত্ত আকারের সাব-ম্যাট্রিক্সের মোট সংখ্যা গণনা করতে হবে যা শুধুমাত্র দুটি বিটের মধ্যে একটি নিয়ে গঠিত অর্থাৎ সাব-ম্যাট্রিক্সের সমস্ত উপাদান 0/1 হবে৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
n = 3 , m = 4
bin[][] = {{ 1, 1, 0, 1}
{ 1, 1, 1, 0}
{ 0, 1, 1, 1}}
q = 1
q1 = (2, 1) আউটপুট
2
ব্যাখ্যা
সমস্ত উপাদান 1 সহ সাইজ 2 এর সমস্ত সাব-ম্যাট্রিক্স হল −
{{ 1, 1, 0, 1}
{ 1, 1, 1, 0}
{ 0, 1, 1, 1}}
{{ 1, 1, 0, 1}
{ 1, 1, 1, 0}
{ 0, 1, 1, 1}} এই সমস্যার সমাধান হল ডাইনামিক প্রোগ্রামিং ব্যবহার করা পন্থা সমাধান করতে, আমরা একই বিটের বৃহত্তম সাবম্যাট্রিক্স সংরক্ষণ করতে একটি 2D ম্যাট্রিক DP[][] বজায় রাখব। অর্থাৎ DP[i][j] সাব-ম্যাট্রিক্সের মান সংরক্ষণ করবে যার শেষ সূচক (i, j), এবং সমস্ত উপাদান একই।
আপনার বোঝার জন্য, যদি DP[4][5] =2, bin[3][4], bin[3][5], bin[4][4] এবং bin[4][5] এর উপাদান একই হয় .
সুতরাং, DP[i][j] খোঁজার জন্য, আমাদের দুটি ক্ষেত্রে আছে −
কেস 1 − যদি i =0 orj =0 :DP[i][j] =1, শুধুমাত্র একটি সাব-ম্যাট্রিক্স সম্ভব হতে পারে।
কেস 2 − অন্যথায়, bin[i-(k-1)][j] =bin[i][j - (k-1)] …:এই ক্ষেত্রে DP[i][j] =min(DP[i][ j-1] , DP[i -1][j], DP[i-1][j-1] ) + 1. এটি আমাদের প্রয়োজন মত সাব-ম্যাট্রিক্সে অবদান রাখবে। সাধারণীকরণ করা যাক, k =2 এর ক্ষেত্রে, অর্থাৎ যদি আমরা 2X2 আকারের একটি সাব-ম্যাট্রিক্স বিবেচনা করি। তারপরে আমাদের পরীক্ষা করতে হবে bin[i][j] =bin[i] [j - 1] =bin[i- 1][j] =bin[i -1 ][j -1 ], যদি এটি সম্ভব হয় তারপর, আমরা k =2 এর জন্য DP[i][j] খুঁজে পাব।
কেস 2 শর্ত পূরণ না হলে, আমরা DP[i][j] =1 সেট করব, যা একটি ডিফল্ট মান হিসাবে বিবেচিত হতে পারে৷
DP[i][j]-এর এই মান একটি সেট বিট বা আনসেট বিটের জন্য হতে পারে। আমরা bin[i][j] এর মান পরীক্ষা করে দেখব যে k এর মানটি কোন সেট বা আনসেট মানগুলির অন্তর্গত। ফ্রিকোয়েন্সি খুঁজে বের করার জন্য, আমরা দুটি অ্যারে তৈরি করব, সাব-ম্যাট্রিক্সের ফ্রিকোয়েন্সি সংরক্ষণ করার জন্য শূন্য ফ্রিকোয়েন্সি যা 0-এর জন্য তৈরি হয়।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include <iostream>
using namespace std;
#define N 3
#define M 4
int min(int a, int b, int c) {
if (a <= b && a <= c)
return a;
else if (b <= a && b <= c)
return b;
else
return c;
}
int solveQuery(int n, int m, int bin[N][M], int x, int y){
int DP[n][m], max = 1;
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 ((bin[i][j] == bin[i - 1][j]) && (bin[i][j] == bin[i][j - 1]) && (bin[i][j] == bin[i - 1][j - 1])) {
DP[i][j] = min(DP[i - 1][j], DP[i - 1][j - 1], DP[i][j - 1]) + 1;
if (max < DP[i][j])
max = DP[i][j];
}
else
DP[i][j] = 1;
}
}
int zeroFrequency[n+m] = { 0 }, oneFrequency[n+m] = { 0 };
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (bin[i][j] == 0)
zeroFrequency[DP[i][j]]++;
else
oneFrequency[DP[i][j]]++;
}
}
for (int i = max - 1; i >= 0; i--) {
zeroFrequency[i] += zeroFrequency[i + 1];
oneFrequency[i] += oneFrequency[i + 1];
}
if (y == 0)
return zeroFrequency[x];
else
return oneFrequency[x];
}
int main(){
int n = 3, m = 4;
int mat[N][M] =
{{ 1, 1, 0, 1},
{ 1, 1, 1, 0},
{ 0, 1, 1, 1}};
int Q = 2;
int query[Q][2] = {{ 2, 1}, { 1, 0}};
for(int i = 0; i < Q; i++){
cout<<"For Query "<<(i+1)<<": The number of Binary sub-matrices of Given size is " <<solveQuery(n, m, mat, query[i][0], query[i][1])<<"\n";
}
return 0;
} আউটপুট
For Query 1: The number of Binary sub-matrices of Given size is 2 For Query 2: The number of Binary sub-matrices of Given size is 3
