C++-এ ম্যাট্রিক্সে সম রেক্ট্যাঙ্গুলার সমের সেল খুঁজুন

একটি m x n ম্যাট্রিক্স দেওয়া আছে। এমন সেল খুঁজতে হবে যেন সেটির হয়etekdu duRectangular sub-matrix (উপরের বাম থেকে সেটি এবং সেটি থেকে নিচের ডান) সমান হয় বাকি সব এলিমেন্টের যোগফলের সাথে।

উদাহরণ

ইনপুট:

mat = {{5,0,2,7},
       {3,0,1,0},
       {1,4,1,3},
       {10,0,2,1}}

আউটপুট: (1, 1) (2, 1)

অ্যালগরিদম: ডাবল অক্সিলিয়ারি ম্যাট্রিক্স

1. aux1[i][j] = (0,0) থেকে (i,j) পর্যন্ত সাবম্যাট্রিক্সের যোগফল।
2. aux2[i][j] = (i,j) থেকে (m-1,n-1) পর্যন্ত সাবম্যাট্রিক্সের যোগফল।
3. প্রতিটি সেলের জন্য: total = aux1[i][j] + aux2[i][j] - mat[i][j] (কারণ mat[i][j] দুবার গণনা হয়েছে)।
4. যদি total == matSum / 2 হয় (যেখানে matSum = পুরো ম্যাট্রিক্সের যোগফল), তবে সেটি উত্তর।

C++ প্রোগ্রাম

#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++) {
            aux1[i][j] = aux2[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)

ব্যাখ্যা

• aux1 = টপ-লেফ্ট থেকে বটম-রাইট প্রিফিক্স সম।
• aux2 = বটম-রাইট থেকে টপ-লেফ্ট প্রিফিক্স সম (রিভার্স)।
• শর্ত: 2*(aux1+aux2-mat[i][j]) == matSum → বাম-উপরের রেক্ট্যাঙ্গেল + ডান-নিচের রেক্ট্যাঙ্গেল = বাকি এলিমেন্টের যোগফল।
• টাইম: O(m×n), স্পেস: O(m×n)।