C++에서 모두 1로 정사각형 부분행렬 계산하기

크기가 m x n인 이진 행렬을 가정합니다. 우리는 모두 1인 제곱 부분행렬의 수를 계산해야 합니다. 따라서 행렬이 다음과 같은 경우 -

따라서 15개의 정사각형이 됩니다. 단일 사각형 10개, 4 사각형 4개, 9개가 있는 사각형 1개.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• set ans :=0, n :=행 개수 및 m :=열 개수
• 0 ~ m – 1 범위의 i에 대해
  • ans :=ans + 행렬[n – 1, i]
• 0 ~ n – 1 범위의 i에 대해
  • ans :=ans + 행렬[i, m – 1]
• ans :=ans – 행렬[n – 1, m – 1]
• n – 2에서 0까지 범위에 있는 i의 경우
  • m – 2에서 0까지 범위에 있는 j의 경우
    • 행렬[i, j] =1이면
      • 행렬[i, j] :=1 + (행렬[i + 1, j + 1], 행렬[i, j + 1], 행렬[i + 1, j])의 최소값
    • 그렇지 않으면 행렬[i,j] :=0
    • ans :=ans + 행렬[i, j]
• 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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