সি++-এ বাইনারি ম্যাট্রিক্সে দেওয়া সাইজের সাব-ম্যাট্রিক্স কয়টি আছে তা কোয়েরি

একটি বাইনারি ম্যাট্রিক্স `bin[n][m]` দেওয়া আছে। `q`টি কোয়েরি আছে। প্রতিটি কোয়েরি `(x, y)` এর জন্য `x*x` সাইজের সাব-ম্যাট্রিক্স কতটি আছে যাদের সব এলিমেন্ট `y` (০ বা ১) তা বের করতে হবে।

সমস্যা বর্ণনা

ডাইনামিক প্রোগ্রামিং (DP) দিয়ে সমাধান। `DP[i][j]` = `(i,j)` এ শেষ হওয়া সবচেয়ে বড় স্কোয়ার সাব-ম্যাট্রিক্স যার সব এলিমেন্ট একই।

উদাহরণ

ইনপুট

n=3, m=4, bin = {{1,1,0,1},{1,1,1,0},{0,1,1,1}}, q=1, query=(2,1)

আউটপুট

2

ব্যাখ্যা — ২x২ সাইজের সব ১ বাড়ি সাব-ম্যাট্রিক্স ২টি।

এলগরিদম

DP[i][j] = 1 যদি i==0 বা j==0
DP[i][j] = min(DP[i-1][j], DP[i][j-1], DP[i-1][j-1]) + 1 যদি bin[i][j]==bin[i-1][j]==bin[i][j-1]==bin[i-1][j-1]
অন্যথায় 1
এরপর ফ্রিকোয়েন্সি অ্যারে বানানো ০ ও ১ এর জন্য, কোয়েরি আন্সার করা।

উদাহরণ কোড

#include <iostream> 
using namespace std; 

#define N 3
#define M 4

int min3(int a, int b, int c){
    if(a<=b && a<=c) return a;
    if(b<=a && b<=c) return b;
    return c;
}

int solveQuery(int n, int m, int bin[N][M], int x, int y){
    int DP[n][m], maxv = 1;
    for(int i=0; i=0; i--){
        zeroF[i] += zeroF[i+1];
        oneF[i] += oneF[i+1];
    }
    return (y==0) ? zeroF[x] : oneF[x];
}

int main(){
    int mat[N][M] = {{1,1,0,1},{1,1,1,0},{0,1,1,1}};
    int Q = 2, query[2][2] = {{2,1},{1,0}};
    for(int i=0; i

আউটপুট
Query 1: 2
Query 2: 3