C++의 주어진 행렬에서 1의 제곱 부분 행렬의 수를 계산하는 프로그램

<시간/>

2차원 이진 행렬이 있다고 가정하고 모두 1인 부분행렬의 총 수를 찾아야 합니다.

따라서 입력이 다음과 같으면

1	1	0
1	1	0
0	0	1

5개의 1 x 1 행렬과 2개의 2 x 1 행렬이 있으므로 출력은 10이 됩니다. 2개의 1 x 2 행렬. 그리고 하나의 2 x 2 매트릭스.

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

getAns() 함수를 정의하면 배열 a가 필요합니다.
렛 :=0
n :=a
의 크기
n
크기의 배열 v 정의
하나의 스택 정의
initialize i :=0의 경우, i
- 동안 (st는 비어 있지 않고 a[st의 최상위 요소]>=a[i]), 수행 -
  - 성에서 팝
- st가 비어 있지 않으면 -
  - prev :=st의 최상위 요소
  - v[i] :=v[i] + v[이전]
  - v[i] :=v[i] + a[i] * (i - 이전)
- 그렇지 않으면
  - v[i] :=v[i] + a[i] * (i + 1)
- i를 st에 삽입
v −
의 각 i에 대해
- 렛 :=렛 + i
리턴 렛
주요 방법에서 다음을 수행하십시오 -
ret :=0
n :=v의 크기
m :=(n이 0이 아니면 v[0]의 크기, 그렇지 않으면 0)
크기가 m인 어레이 온도 정의
initialize i :=0의 경우, i
- j 초기화의 경우:=0, j
  - temp[j] :=(v[i, j]가 0이 아니면 temp[j] + 1, 그렇지 않으면 0)
- ret :=ret + getAns(temp)
리턴 렛

예시

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

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