有关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 = 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值属于哪个设置值或未设置值。为了找到频率,我们将创建两个数组,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