数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中给定大小的二进制子矩阵数量查询
在这个问题中，我们给定一个大小为 nXm 的二进制矩阵 bin[][]。我们的任务是解决所有 q 个查询。对于查询(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
解释
所有元素都为 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}}这个问题的解决方案是使用**动态规划**方法。为了解决这个问题，我们将维护一个二维矩阵 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 或 j = 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
89 次浏览
