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}};
출력
10