有关C ++中给定大小的二进制子矩阵数量的查询
在这个问题中，我们得到了大小为nXm的二进制矩阵bin[][]。我们的任务是解决所有q个查询。对于query(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
说明
大小为2且所有元素为1的所有子矩阵均为-
{{ 1, 1, 0, 1}
{ 1, 1, 1, 0}
{ 0, 1, 1, 1}}
{{ 1, 1, 0, 1}
{ 1, 1, 1, 0}
{ 0, 1, 1, 1}}解决此问题的方法是使用动态编程方法。为了解决这个问题，我们将维护一个二维矩阵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=0orj=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值属于哪个设置值或未设置值。为了找到频率，我们将创建两个数组，zeroFrequrency存储为0生成的子矩阵的频率。oneFrequrency存储为1生成的子矩阵的频率。
该程序说明了我们解决方案的工作原理，
示例
#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