用C ++全数计数平方子矩阵

假设我们有一个大小为mx n的二进制矩阵。我们必须计算平方全为1的子矩阵。所以如果矩阵像-

因此将有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