在 C++ 中计算全为 1 的平方子矩阵
c++server side programmingprogramming更新于 2024/9/28 0:39:00
假设我们有一个大小为 m x n 的二进制矩阵。我们必须计算全为 1 的平方子矩阵的数量。因此，如果矩阵为 −
| 0 | 1 | 1 | 1 |
|---|---|---|---|
| 1 | 1 | 1 | |
| 0 | 1 | 1 | 1 |
因此，将有 15 个平方。 10 个单数方格，4 个四数方格，以及 1 个九数方格。
为了解决这个问题，我们将遵循以下步骤 −
- 设置 ans := 0，n := 行数和 m := 列数
- 对于 i 在 0 到 m – 1 范围内
- ans := ans + matrix[n – 1, i]
- 对于 i 在 0 到 n – 1 范围内
- ans := ans + matrix[i, m – 1]
- ans := ans – matrix[n – 1, m - 1]
- 对于 i，范围从 n 到 2，向下到 0
- 对于 j，范围从 m 到 2，向下到 0
- 如果 matrix[i, j] = 1，则
- matrix[i, j] := 1 + (matrix[i + 1, j + 1], matrix[i, j + 1], matrix[i + 1, j]) 的最小值
- 否则 matrix[i,j] := 0
- ans := ans + matrix[i, j]
- 如果 matrix[i, j] = 1，则
- 对于 j，范围从 m 到 2，向下到 0
- return ans
让我们看看下面的实现以便更好地理解 −
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
int ans = 0;
int n = matrix.size();
int m = matrix[0].size();
for(int i = 0; i < m; i++)ans += matrix[n-1][i];
for(int i = 0; i < n; i++)ans += matrix[i][m-1];
ans -= matrix[n-1][m-1];
for(int i = n - 2;i >= 0; i--){
for(int j = m-2 ;j >= 0; j--){
matrix[i][j] = matrix[i][j] == 1? 1 + min({matrix[i+1][j+1],matrix[i] [j+1],matrix[i+1][j]}) : 0;
ans += matrix[i][j];
}
}
return ans;
}
};
main(){
vector<vector<int>> v = {{0,1,1,1},{1,1,1,1},{0,1,1,1}};
Solution ob;
cout << (ob.countSquares(v));
}
输入
[[0,1,1,1], [1,1,1,1], [0,1,1,1]]
输出
15
