有关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

以上是 有关C ++中给定大小的二进制子矩阵数量的查询 的全部内容, 来源链接: utcz.com/z/327049.html

回到顶部