मान लीजिए कि हमारे पास एक मैट्रिक्स है, और एक लक्ष्य मूल्य है, हमें गैर-रिक्त सबमैट्रिसेस की संख्या का पता लगाना है जो योग लक्ष्य के समान है। यहां एक सबमैट्रिक्स [(x1, y1), (x2, y2)] सभी सेल मैट्रिक्स [x] [y] का सेट है, जिसमें x रेंज x1 और x2 और y रेंज y1 और y2 में है। दो सबमैट्रिस [(x1, y1), (x2, y2)] और [(x1', y1'), (x2', y2')] अलग हैं यदि उनके पास कुछ निर्देशांक हैं जो अलग हैं:जैसे, यदि x1 नहीं है X1' के समान।
तो, अगर इनपुट पसंद है
| 0 | 1 | 0 |
| 1 | 1 | 1 |
| 0 | 1 | 0 |
और लक्ष्य =0, तो आउटपुट 4 होगा, ऐसा इसलिए है क्योंकि चार 1x1 सबमैट्रिस जिसमें केवल 0 होता है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
उत्तर:=0
-
col :=स्तंभों की संख्या
-
पंक्ति :=पंक्तियों की संख्या
-
इनिशियलाइज़ करने के लिए:=0, जब मैं <पंक्ति, अपडेट (i 1 से बढ़ाएँ), करें -
-
इनिशियलाइज़ j :=1 के लिए, जब j
-
मैट्रिक्स [i, j]:=मैट्रिक्स [i, j] + मैट्रिक्स [i, j - 1]
-
-
-
एक नक्शा परिभाषित करें मी
-
इनिशियलाइज़ करने के लिए मैं :=0, जब i
-
इनिशियलाइज़ j :=i के लिए, जब j
-
नक्शा साफ़ करें मी
-
मी[0] :=1
-
योग :=0
-
-
k :=0 को इनिशियलाइज़ करने के लिए, जब k <रो, अपडेट (k को 1 से बढ़ाएँ), करें -
-
वर्तमान:=मैट्रिक्स [के, जे]
-
अगर मैं - 1>=0, तो -
-
करंट:=करंट - मैट्रिक्स [k, i - 1]
-
-
योग :=योग + वर्तमान
-
उत्तर:=उत्तर + एम [लक्ष्य - योग]
-
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
