資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告