এই সমস্যায়, আমাদের একটি ম্যাট্রিক্স mat দেওয়া হয়েছে পূর্ণসংখ্যা মানের mXn আকার। আমাদের কাজ হল একটি ম্যাট্রিক্সে একই আয়তক্ষেত্রাকার যোগফল সহ কোষ মুদ্রণ করার জন্য একটি প্রোগ্রাম তৈরি করা .
সমস্যা বর্ণনা: আমরা ম্যাট্রিক্সে এমনভাবে একটি ঘর খুঁজে পাব যাতে সাব-ম্যাট্রিক্সের যোগফল যা ঘরের সাথে শুরু হয় এবং শেষ হয় তা সমস্ত অবশিষ্ট উপাদানগুলির যোগফলের সমান হয়।
একটি ঘরের জন্য ম্যাট্রিক্স (a, b) সাব-ম্যাট্রিক্স ম্যাট[0][0] থেকে ম্যাট[a][b] এবং ম্যাট[a][b] থেকে ম্যাট[m][n] এর সমষ্টি সমস্ত অবশিষ্ট উপাদানের যোগফল।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট: ম্যাট[][] ={ {5, 0, 2, 7}
{3, 0, 1, 0}
{1, 4, 1, 3}
{10, 0, 2, 1}}
আউটপুট: (2, 1)
ব্যাখ্যা:
উপাদানের জন্য (2,3)
সাবম্যাট্রিক্স1 হল - { {5, 0}
{3, 0}
{1, 4}}
সাবম্যাট্রিক্স২ হল - {{4, 1, 3}
{0, 2, 1}}
যোগফল =5 + 0 + 3 + 0 + 1 + 4 + 1 + 3 + 0 + 2 + 1 =20
বাকি উপাদানের যোগফল =2 + 7 + 1 + 0 + 10 =20
সমাধান পদ্ধতি
সমস্যা সমাধানের জন্য, আমাদের 2টি সহায়ক উপ-ম্যাট্রিস তৈরি করতে হবে, aux1[m][n] এবং aux2[m][n]। aux1[i][j] (0,0) থেকে (i, j) পর্যন্ত সমস্ত উপাদানের যোগফল সংরক্ষণ করবে এবং aux2[i][j] (i,j) থেকে (i,j) পর্যন্ত সমস্ত উপাদানের যোগফল সংরক্ষণ করবে n, মি)। তারপর আমরা উভয় যোগফল যোগ করব এবং বিয়োগ করব mat(i,j) কারণ এটি দুবার হবে।
তারপর আমরা এই যোগফলটিকে ম্যাট্রিক্সের সমস্ত উপাদানের যোগফলের সাথে তুলনা করব। কক্ষে যোগফল ম্যাট্রিক্সের যোগফলের অর্ধেক হলে। তারপর সেলটি ফলাফল, এবং আমরা এটি প্রিন্ট করব।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include <iostream>
using namespace std;
#define R 4
#define C 4
void findCellWithSameRectSum(int mat[R][C]) {
int m = R, n = C;
int aux1[m][n], aux2[m][n];
int matSum = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
aux2[i][j] = aux1[i][j] = mat[i][j];
matSum += mat[i][j];
}
}
for (int i = 1; i < m; i++) {
aux1[i][0] += aux1[i-1][0];
aux2[m-i-1][n-1] += aux2[m-i][n-1];
}
for (int j = 1; j < n; j++) {
aux1[0][j] += aux1[0][j-1];
aux2[m-1][n-j-1] += aux2[m-1][n-j];
}
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++) {
aux1[i][j] += aux1[i-1][j] + aux1[i][j-1] - aux1[i-1][j-1];
aux2[m-i-1][n-j-1] += aux2[m-i][n-j-1] + aux2[m-i-1][n-j] - aux2[m-i][n-j];
}
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (matSum == 2 * (aux1[i][j] + aux2[i][j] - mat[i][j]))
cout << "(" << i << ", " << j << ")\t";
}
int main() {
int mat[R][C] = {{5, 0, 2, 7},
{3, 0, 1, 0},
{1, 4, 1, 3},
{10, 0, 2, 1}};
cout<<"The cells with same rectangular sums in a matrix is \n";
findCellWithSameRectSum(mat);
return 0;
} আউটপুট
The cells with same rectangular sums in a matrix is (1, 1) (2, 1)
