행렬과 목표 값이 있다고 가정하고 합계가 목표와 동일한 비어 있지 않은 부분행렬의 수를 찾아야 합니다. 여기서 부분행렬 [(x1, y1), (x2, y2)]은 x1 및 x2 범위에 x가 있고 y1 및 y2 범위에 y가 있는 모든 셀 행렬[x][y]의 집합입니다. 두 부분행렬 [(x1, y1), (x2, y2)] 및 [(x1', y1'), (x2', y2')]는 서로 다른 좌표가 있는 경우 다릅니다. 예를 들어 x1이 그렇지 않은 경우 x1'과 동일합니다.
따라서 입력이 다음과 같으면
| 0 | 1 | 0 |
| 1 | 1 | 1 |
| 0 | 1 | 0 |
target =0이면 출력은 4가 됩니다. 이는 0만 포함하는 4개의 1x1 부분행렬 때문입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
답변 :=0
-
col :=열 수
-
행 :=행 수
-
initialize i :=0의 경우 i
-
j 초기화의 경우 :=1, j
-
행렬[i, j] :=행렬[i, j] + 행렬[i, j - 1]
-
-
-
하나의 맵 정의
-
initialize i :=0의 경우 i
-
j를 초기화하기 위해 :=i, j
-
지도 지우기 m
-
m[0] :=1
-
합계 :=0
-
-
초기화 k :=0의 경우, k <행일 때 업데이트(k를 1만큼 증가), 수행 -
-
현재 :=행렬[k, j]
-
i - 1>=0이면 -
-
현재 :=현재 - 행렬[k, i - 1]
-
-
합계 :=합계 + 현재
-
ans :=ans + m[목표 - 합계]
-
m[-sum]을 1 증가
-
-
-
반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numSubmatrixSumTarget(vector<vector<int>>& matrix, int
target) {
int ans = 0;
int col = matrix[0].size();
int row = matrix.size();
for(int i = 0; i < row; i++){
for(int j = 1; j < col; j++){
matrix[i][j] += matrix[i][j - 1];
}
}
unordered_map <int, int> m;
for(int i = 0; i < col; i++){
for(int j = i; j < col; j++){
m.clear();
m[0] = 1;
int sum = 0;
for(int k = 0; k < row; k++){
int current = matrix[k][j];
if(i - 1 >= 0)current -= matrix[k][i - 1];
sum += current;
ans += m[target - sum];
m[-sum]++;
}
}
}
return ans;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{0,1,0},{1,1,1},{0,1,0}};
cout << (ob.numSubmatrixSumTarget(v, 0));
} 입력
{{0,1,0},{1,1,1},{0,1,0}}, 0 출력
4