Count Square Submatrices với All Ones trong C ++

Giả sử chúng ta là một ma trận nhị phân, kích thước m x ​​n. Chúng ta phải đếm số lượng ma trận con vuông, với tất cả các số 1. Vì vậy, nếu ma trận giống như -

Vậy sẽ có 15 ô vuông. 10 hình vuông đơn lẻ, 4 hình vuông bốn hình vuông và 1 hình vuông có chín hình vuông.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• đặt ans:=0, n:=số hàng và m:=số cột
• cho tôi trong phạm vi từ 0 đến m - 1
  • ans:=ans + matrix [n - 1, i]
• cho tôi trong phạm vi từ 0 đến n - 1
  • ans:=ans + matrix [i, m - 1]
• ans:=ans - matrix [n - 1, m - 1]
• đối với tôi trong phạm vi n - 2 giảm xuống 0
  • cho j trong phạm vi m - 2 giảm xuống 0
    • nếu ma trận [i, j] =1, thì
      • ma trận [i, j]:=1 + tối thiểu của (ma trận [i + 1, j + 1], ma trận [i, j + 1], ma trận [i + 1, j])
    • nếu không thì ma trận [i, j]:=0
    • ans:=ans + matrix [i, j]
• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

[[0,1,1,1],
[1,1,1,1],
[0,1,1,1]]

Đầu ra

15