C++中求非零子矩阵个数的程序
假设我们有一个只包含两个值的矩阵；1和0。我们必须找出给定矩阵中包含全1的子矩阵的数量。我们将值打印为输出。
所以，如果输入是这样的
那么输出将是12。
示例
让我们看看以下实现以获得更好的理解-
#include<bits/stdc++.h>
using namespace std;
int solve(vector<vector<int>>& matrix) {
int n = matrix.size();
int m = matrix[0].size();
int add[n + 1][m + 1];
memset(add, 0, sizeof(add));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
add[i + 1][j + 1] += matrix[i][j];
add[i + 1][j + 1] += add[i][j + 1];
add[i + 1][j + 1] += add[i + 1][j];
add[i + 1][j + 1] -= add[i][j];
}
}
int res = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!matrix[i][j])
continue;
for (int k = 1; k <= (n - i); k++) {
int p = 0,
q = m - j;
int r;
while (p <= q) {
int x = (p + q) / 2;
int a = k * x;
int cur = add[i + k][j + x] - add[i][j + x] - add[i + k][j] + add[i][j];
if (cur == a) {
r = x;
p = x + 1;
} else
q = x - 1;
}
if (r == 0)
break;
res += r;
}
}
}
return res;
}
int main() {
vector<vector<int>> mat = {{0, 0, 1, 0}, {0, 1, 0, 0}, {0, 1, 0, 1}, {1, 1, 0, 1}};
cout<< solve(mat) <<endl;
return 0;
}输入
{{0, 0, 1, 0}, {0, 1, 0, 0}, {0, 1, 0, 1}, {1, 1, 0, 1}}输出结果12
热门推荐
10 买房的祝福语高级简短
11 分手毕业祝福语简短女生
12 茶人生日祝福语简短
13 亲戚红包生日祝福语简短
14 创业失败返乡祝福语简短
15 周末祝福语简短老师的话
16 虎年新年专属祝福语简短
17 硕士毕业蛋糕祝福语简短
18 新婚祝福语有趣文案简短