मान लीजिए हमारे पास एक मैट्रिक्स है और एक लक्ष्य मान है, हमें उन गैर-खाली सबमैट्रिक्स की संख्या ढूंढनी है जिनका योग लक्ष्य के बराबर है। यहां एक सबमैट्रिक्स [(x1, y1), (x2, y2)] उन सभी सेल्स matrix[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 है।
हल करने का दृष्टिकोण
इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
ans := 0
col := कॉलम की संख्या
row := पंक्तियों की संख्या
प्रत्येक पंक्ति के लिए प्रीफिक्स योग की गणना करें
दो कॉलम सीमाओं (i, j) के बीच सभी संभावित जोड़ों के लिए पुनरावृति करें
प्रत्येक जोड़ी के लिए, पंक्तियों के साथ 1D सरणी के रूप में उपसमस्या को हल करने के लिए हैश मैप का उपयोग करें
वर्तमान योग और लक्ष्य के बीच अंतर की आवृत्ति को ट्रैक करें
मान्य सबमैट्रिक्स की संख्या संचित करें
उदाहरण
#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;
// पंक्तियों को 1D सरणी के रूप में संसाधित करें
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;
}
};
int main(){
Solution ob;
vector<vector<int>> v = {{0,1,0},{1,1,1},{0,1,0}};
cout << (ob.numSubmatrixSumTarget(v, 0));
return 0;
}
इनपुट
{{0,1,0},{1,1,1},{0,1,0}}, 0
आउटपुट
4