用C ++全数计数平方子矩阵
假设我们有一个大小为mxn的二进制矩阵。我们必须计算平方全为1的子矩阵。所以如果矩阵像-
01101因此将有15个正方形。单人10平方，四人4平方，以及1平方和9平方。
为了解决这个问题，我们将遵循以下步骤-
设置ans：=0，n：=行数和m：=列数
当我的范围是0到m–1
ans：=ans+matrix[n–1，i]
对于i，范围为0至n–1
ans：=ans+matrix[i，m–1]
ans：=ans–矩阵[n–1，m-1]
当我在n–2范围内下降到0
如果matrix[i，j]=1，则
否则matrix[i，j]：=0
ans：=ans+matrix[i，j]
矩阵[i，j]：=1+（矩阵[i+1，j+1]，矩阵[i，j+1]，矩阵[i+1，j]的最小值）
对于范围m–2中的j降低到0
返回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