程序在C ++中计算给定矩阵中1s的平方子矩阵的数量

• Z时代
• 2024-01-10
• 分类：综合

假设我们有一个二维二进制矩阵，我们必须找到所有1 s的子矩阵总数。

所以，如果输入像

那么输出将是10，因为有五个1 x 1矩阵，两个2 x 1矩阵。两个1 x 2矩阵。和一个2 x 2矩阵。

示例

让我们看下面的实现以更好地理解-

#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

以上是 程序在C ++中计算给定矩阵中1s的平方子矩阵的数量 的全部内容， 来源链接： utcz.com/z/347092.html