数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++程序：查找非零子矩阵的数量
假设我们得到一个矩阵，其中只包含两个值：1 和 0。我们需要找到给定矩阵中包含全为 1 的子矩阵的数量。我们将输出该值。
因此，如果输入如下所示：
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 |
则输出将为 12。
为了解决这个问题，我们将遵循以下步骤：
- n := 矩阵的大小
- m := matrix[0] 的大小
- 定义一个大小为 n+1 x m+1 的数组 add。
- 初始化 i := 0，当 i < n 时，更新（i 加 1），执行：
- 初始化 j := 0，当 j < m 时，更新（j 加 1），执行：
- 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]
- 初始化 j := 0，当 j < m 时，更新（j 加 1），执行：
- res := 0
- 初始化 i := 0，当 i < n 时，更新（i 加 1），执行：
- 初始化 j := 0，当 j < m 时，更新（j 加 1），执行：
- 如果 matrix[i, j] 不为零，则：
- 忽略以下部分，跳到下一次迭代
- 初始化 k := 1，当 k <= (n - i) 时，更新（k 加 1），执行：
- p := 0,
- q := m - j;
- 当 p <= q 时，执行：
- x := (p + q) / 2
- a := k * x
- cur := add[i + k, j + x] - add[i, j + x] - add[i + k, j] + add[i, j]
- 如果 cur 等于 a，则：
- r := x
- p := x + 1
- 否则，
- q := x - 1
- 如果 r 等于 0，则：
- 退出循环
- res := res + r
- 如果 matrix[i, j] 不为零，则：
- 初始化 j := 0，当 j < m 时，更新（j 加 1），执行：
- 返回 res
示例
让我们看一下以下实现，以便更好地理解：
#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
更新于: 2021年10月16日
420 次浏览
广告