C++で指定されたサイズのバイナリサブ行列の数に関するクエリ

この問題では、サイズnXmのバイナリ行列bin[][]が与えられます。私たちのタスクは、すべてのqクエリを解決することです。 query（x、y）の場合、配列yのすべての要素（2進数）となるようなサイズx*xの部分行列の数を見つける必要があります。

問題の説明

ここでは、2つのビットのうちの1つだけで構成される、特定のサイズのサブマトリックスの総数をカウントする必要があります。つまり、サブマトリックスはすべての要素を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]を見つけるには、2つのケースがあります-

ケース1 − i=0またはj=0の場合：DP [i] [j] =1、可能なサブマトリックスは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値が設定値または未設定値のどちらに属するかを確認します。頻度を見つけるために、2つの配列を作成します。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