程序在C ++中计算给定矩阵中1s的平方子矩阵的数量
假设我们有一个二维二进制矩阵，我们必须找到所有1s的子矩阵总数。
所以，如果输入像
那么输出将是10，因为有五个1x1矩阵，两个2x1矩阵。两个1x2矩阵。和一个2x2矩阵。
示例
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int getAns(vector& a) {
int ret = 0;
int n = a.size();
vector<int> v(n);
stack<int> st;
for (int i = 0; i < a.size(); i++) {
while (!st.empty() && a[st.top()] >= a[i])
st.pop();
if(!st.empty()) {
int prev = st.top();
v[i] += v[prev];
v[i] += a[i] * (i - prev);
}
else{
v[i] += a[i] * (i + 1);
}
st.push(i);
}
for (int i : v) {
ret += i;
}
return ret;
}
int solve(vector<vector<int>>& v) {
int ret = 0;
int n = v.size();
int m = n ? v[0].size() : 0;
vector<int> temp(m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
temp[j] = v[i][j] ? temp[j] + 1 : 0;
}
ret += getAns(temp);
}
return ret;
}
};
int solve(vector<vector<int>>& matrix) {
return (new Solution())->solve(matrix);
}
main(){
vector<vector> matrix = {
{1, 1, 0},
{1, 1, 0},
{0, 0, 1}
};
cout << solve(matrix);
}输入值
{{1, 1, 0},{1, 1, 0},{0, 0, 1}};输出结果10