मान लीजिए कि हमारे पास एक 2D मैट्रिक्स है जिसे मैट्रिक्स कहा जाता है, हमें (row1, col1) का उपयोग करके (row1, col1) और निचले दाएं कोने द्वारा परिभाषित आयत के अंदर तत्वों का योग ज्ञात करना होगा ( row2, col2)।
तो अगर मैट्रिक्स की तरह है -
| 3 | 0 | 1 | 4 | 2 |
| 5 | 6 | 3 | 2 | 1 |
| 1 | 2 | 0 | 1 | 5 |
| 4 | 1 | 0 | 1 | 7 |
| 1 | 0 | 3 | 0 | 5 |
उपरोक्त आयत में नीला रंग (2,1) और (4,3) द्वारा परिभाषित है, इसमें योग 8 है।
इसलिए यदि हम कुछ क्वेरी जैसे sumRegion(2, 1, 4, 3), sumRegion(1, 1, 2, 2), sumRegion(1, 2, 2, 4) करते हैं, तो ये क्रमशः 8, 11, 12 वापस आ जाएंगे।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
dp नामक मैट्रिक्स को परिभाषित करें।
-
कार्य को इस प्रकार प्रारंभ करें
-
n:=पंक्तियों की संख्या। अगर n 0 है, तो वापस लौटें,
-
मी :=स्तंभों की संख्या
-
dp :=आकार का एक और मैट्रिक्स n x m
-
मेरे लिए 0 से n की सीमा में
-
j के लिए 0 से m की सीमा में
-
जब j – 1 <0, तब dp[i, j] को मैट्रिक्स के रूप में सेट करें[i, j], अन्यथा इसे (dp[i, j-1] + मैट्रिक्स[i, j])
के रूप में सेट करें
-
-
-
मैं के लिए 1 से n की सीमा में
-
j के लिए 0 से m की सीमा में
-
बढ़ाएँ dp[i, j] द्वारा dp[i – 1, j]
-
-
-
क्वेरी विधि के लिए, यह row1, col1, row2, col2 को लेगा
-
रिट:=डीपी [पंक्ति 2, col2]
-
उप 1:=0 जब पंक्ति 1 – 1 <0, अन्यथा यह डीपी [पंक्ति 1 – 1, कोल 2] होगा
-
sub2:=0 जब col1 - 1 <0, अन्यथा यह dp[row2, col1 - 1]
होगा -
यदि पंक्ति 1 - 1 <0 या col1 - 1 <0, तो
-
जोड़ें :=0
-
-
अन्यथा जोड़ें :=dp[row1 – 1, col1 – 1]
-
रिटर्न रिट - सब1 - सब2 + ऐड
उदाहरण(C++)
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h>
using namespace std;
class NumMatrix {
public:
vector < vector <int>> dp;
NumMatrix(vector<vector<int>>& matrix) {
int n = matrix.size();
if(!n) return;
int m = matrix[0].size();
dp = vector < vector <int>>(n, vector <int> (m));
for(int i = 0; i < n; i++){
for(int j = 0 ;j < m; j++){
dp[i][j] = j - 1 < 0 ? matrix[i][j] : dp[i][j - 1] + matrix[i][j];
}
}
for(int i = 1; i < n; i++){
for(int j = 0; j < m; j++){
dp[i][j] += dp[i - 1][j];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
int ret = dp[row2][col2];
int sub1 = row1 - 1 < 0 ? 0 : dp[row1 - 1][col2];
int sub2 = col1 - 1 < 0 ? 0 : dp[row2][col1 - 1];
int add = row1 - 1 < 0 || col1 - 1 < 0 ? 0 : dp[row1 - 1][col1 - 1];
return ret - sub1 - sub2 + add;
}
};
main(){
vector<vector<int>> mat = {{3,0,1,4,2},{5,6,3,2,1},{1,2,0,1,5},{4,1,0,1,7},{1,0,3,0,5}};
NumMatrix ob(mat);
cout << ob.sumRegion(2,1,4,3) << endl;
cout << ob.sumRegion(1,1,2,2) << endl;
cout << ob.sumRegion(1,2,2,4) << endl;
} इनपुट
[[3,0,1,4,2], [5,6,3,2,1], [1,2,0,1,5], [4,1,0,1,7], [1,0,3,0,5]] sumRegion(2,1,4,3) sumRegion(1,1,2,2) sumRegion(1,2,2,4)
आउटपुट
8 11 12