এই সমস্যায়, আমাদেরকে পূর্ণসংখ্যা মানের একটি 2D অ্যারে দেওয়া হয়েছে [][]। আমাদের কাজ হল ম্যাটের উপসর্গ যোগ ম্যাট্রিক্স প্রিন্ট করা।
উপসর্গ যোগ ম্যাট্রিক্স: ম্যাট্রিক্সের প্রতিটি উপাদান হল উপরের এবং বাম উপাদানগুলির যোগফল। অর্থাৎ
prefixSum[i][j] = mat[i][j] + mat[i-1][j]...mat[0][j] + mat[i][j-1] +... mat[i][0].
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক
Input: arr =[ [4 6 1] [5 7 2] [3 8 9] ] Output:[ [4 10 11] [9 22 25] [12 33 45] ]
এই সমস্যাটি সমাধান করার জন্য, একটি সহজ সমাধান হল i,j অবস্থান পর্যন্ত সমস্ত উপাদান অতিক্রম করে প্রিফিক্সসাম খুঁজে বের করা এবং তাদের যোগ করা। কিন্তু সিস্টেমের জন্য এটা একটু জটিল।
প্রিফিক্সসাম ম্যাট্রিক্সের উপাদানগুলির মান খুঁজে বের করার জন্য একটি আরও কার্যকর সমাধান হবে।
ij অবস্থানে উপাদানের সাধারণ সূত্র হল
prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1] + a[i][j]
কিছু specail কেস হল
For i = j = 0, prefixSum[i][j] = a[i][j] For i = 0 and j > 0, prefixSum[i][j] = prefixSum[i][j-1] + a[i][j] For i > 0 and j = 0, prefixSum[i][j] = prefixSum[i-1][j] + a[i][j]
আমাদের সমাধানের বাস্তবায়ন দেখানোর কোড
উদাহরণ
#include <iostream>
using namespace std;
#define R 3
#define C 3
void printPrefixSum(int a[][C]) {
int prefixSum[R][C];
prefixSum[0][0] = a[0][0];
for (int i = 1; i < C; i++)
prefixSum[0][i] = prefixSum[0][i - 1] + a[0][i];
for (int i = 0; i < R; i++)
prefixSum[i][0] = prefixSum[i - 1][0] + a[i][0];
for (int i = 1; i < R; i++) {
for (int j = 1; j < C; j++)
prefixSum[i][j]=prefixSum[i- 1][j]+prefixSum[i][j- 1]-prefixSum[i- 1][j- 1]+a[i][j];
}
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++)
cout<<prefixSum[i][j]<<"\t";
cout<<endl;
}
}
int main() {
int mat[R][C] = {
{ 1, 2, 3},
{ 4, 5, 6},
{ 7, 8, 9}
};
cout<<"The prefix Sum Matrix is :\n";
printPrefixSum(mat);
return 0;
} আউটপুট
The prefix Sum Matrix is : 1 3 6 5 12 21 12 27 45
